45. FOCS 2004: Rome, Italy

45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings. IEEE Computer Society 2004, ISBN 0-7695-2228-9 BibTeX

Session 1

Carlos Mochon:
Quantum Weak Coin-Flipping with Bias of 0.192. 2-11
Electronic Edition (link) BibTeX
Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. 12-21
Electronic Edition (link) BibTeX
Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. 22-31
Electronic Edition (link) BibTeX
Mario Szegedy:
Quantum Speed-Up of Markov Chain Based Algorithms. 32-41
Electronic Edition (link) BibTeX
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. 42-51
Electronic Edition (link) BibTeX

Session 2

Moses Charikar, Anthony Wirth:
Maximizing Quadratic Programs: Extending Grothendieck's Inequality. 54-60
Electronic Edition (link) BibTeX
Lap Chi Lau:
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. 61-70
Electronic Edition (link) BibTeX
Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs. 71-80
Electronic Edition (link) BibTeX
Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Machine Minimization for Scheduling Jobs with Interval Constraints. 81-90
Electronic Edition (link) BibTeX

Session 3

Jirí Matousek, Tibor Szabó:
Random Edge Can Be Exponential on Abstract Cubes. 92-100
Electronic Edition (link) BibTeX
Moses Charikar, Michel X. Goemans, Howard J. Karloff:
On the Integrality Ratio for Asymmetric TSP. 101-107
Electronic Edition (link) BibTeX
Julia Chuzhoy, Joseph Naor:
The Hardness of Metric Labeling. 108-114
Electronic Edition (link) BibTeX
Matthew Andrews:
Hardness of Buy-at-Bulk Network Design. 115-124
Electronic Edition (link) BibTeX

Session 4

Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in Lattices. 126-135
Electronic Edition (link) BibTeX
Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. 136-145
Electronic Edition (link) BibTeX
Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? 146-154
Electronic Edition (link) BibTeX
Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. 155-164
Electronic Edition (link) BibTeX

Session 5

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Cryptography in NC⁰. 166-175
Electronic Edition (link) BibTeX
Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge. 176-185
Electronic Edition (link) BibTeX
Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass:
Universally Composable Protocols with Relaxed Set-Up Assumptions. 186-195
Electronic Edition (link) BibTeX
Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai:
On the (Im)possibility of Cryptography with Imperfect Randomness. 196-205
Electronic Edition (link) BibTeX

Session 6

Brian C. Dean, Michel X. Goemans, Jan Vondrák:
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. 208-217
Electronic Edition (link) BibTeX
Anupam Gupta, R. Ravi, Amitabh Sinha:
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. 218-227
Electronic Edition (link) BibTeX
David B. Shmoys, Chaitanya Swamy:
Stochastic Optimization is (Almost) as easy as Deterministic Optimization. 228-237
Electronic Edition (link) BibTeX
Sanjeev Arora, Elad Hazan, Satyen Kale:
0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n²) Time. 238-247
Electronic Edition (link) BibTeX
Marcin Mucha, Piotr Sankowski:
Maximum Matchings via Gaussian Elimination. 248-255
Electronic Edition (link) BibTeX

Session 7

Rahul Savani, Bernhard von Stengel:
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. 258-267
Electronic Edition (link) BibTeX
George Karakostas, Stavros G. Kolliopoulos:
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. 268-276
Electronic Edition (link) BibTeX
Lisa Fleischer, Kamal Jain, Mohammad Mahdian:
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. 277-285
Electronic Edition (link) BibTeX
Kamal Jain:
A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. 286-294
Electronic Edition (link) BibTeX
Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
The Price of Stability for Network Design with Fair Cost Allocation. 295-304
Electronic Edition (link) BibTeX

Session 8

Leslie G. Valiant:
Holographic Algorithms (Extended Abstract). 306-315
Electronic Edition (link) BibTeX
Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. 316-324
Electronic Edition (link) BibTeX
Michael Langberg:
Private Codes or Succinct Random Codes That Are (Almost) Perfect. 325-334
Electronic Edition (link) BibTeX
Qi Cheng, Daqing Wan:
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). 335-341
Electronic Edition (link) BibTeX

Session 9

Ran Raz:
Multilinear-NC neq Multilinear-NC. 344-351
Electronic Edition (link) BibTeX
Steve Chien, Alistair Sinclair:
Algebras with Polynomial Identities and Computing the Determinant. 352-361
Electronic Edition (link) BibTeX
Dorit Aharonov, Oded Regev:
Lattice Problems in NP cap coNP. 362-371
Electronic Edition (link) BibTeX
Daniele Micciancio, Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures. 372-381
Electronic Edition (link) BibTeX

Session 10

Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. 384-393
Electronic Edition (link) BibTeX
Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. 394-403
Electronic Edition (link) BibTeX
Yonatan Bilu, Nathan Linial:
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. 404-412
Electronic Edition (link) BibTeX
Tali Kaufman, Dana Ron:
Testing Polynomials over General Fields. 413-422
Electronic Edition (link) BibTeX
Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman:
Testing Low-Degree Polynomials over Prime Fields. 423-432
Electronic Edition (link) BibTeX

Session 11

Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics. 434-443
Electronic Edition (link) BibTeX
Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler:
Triangulation and Embedding Using Small Sets of Beacons. 444-453
Electronic Edition (link) BibTeX
Amit Kumar, Yogish Sabharwal, Sandeep Sen:
A Simple Linear Time (1+ ) -Approximation Algorithm for k-Means Clustering in Any Dimensions. 454-462
Electronic Edition (link) BibTeX
Nir Halman:
On the Power of Discrete and of Lexicographic Helly-Type Theorems. 463-472
Electronic Edition (link) BibTeX
Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. 473-482
Electronic Edition (link) BibTeX

Session 12

Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality -- Almost. 484-490
Electronic Edition (link) BibTeX
Gianni Franceschini, Roberto Grossi:
No Sorting? Better Searching! 491-498
Electronic Edition (link) BibTeX
Liam Roditty, Uri Zwick:
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. 499-508
Electronic Edition (link) BibTeX
Piotr Sankowski:
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). 509-517
Electronic Edition (link) BibTeX

Session 13

Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
Dynamic Speed Scaling to Manage Energy and Temperature. 520-529
Electronic Edition (link) BibTeX
John Augustine, Sandy Irani, Chaitanya Swamy:
Optimal Power-Down Strategies. 530-539
Electronic Edition (link) BibTeX
Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl:
On the Streaming Model Augmented with a Sorting Primitive. 540-549
Electronic Edition (link) BibTeX
Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
Approximating Edit Distance Efficiently. 550-559
Electronic Edition (link) BibTeX

Session 14

Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
trong Spatial Mixing for Lattice Graphs with Fewer Colours. 562-571
Electronic Edition (link) BibTeX
Elchanan Mossel, Yuval Peres, Alistair Sinclair:
Shuffling by Semi-Random Transpositions. 572-581
Electronic Edition (link) BibTeX
Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda:
Randomly Coloring Constant Degree Graphs. 582-589
Electronic Edition (link) BibTeX
Harold S. Connamacher, Michael Molloy:
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem. 590-599
Electronic Edition (link) BibTeX

Session 15

Anirban Dasgupta, John E. Hopcroft, Frank McSherry:
Spectral Analysis of Random Graphs with Skewed Degree Distributions. 602-610
Electronic Edition (link) BibTeX
Laurence Bisht, Nader H. Bshouty, Lawrance Khoury:
Learning with Errors in Answers to Membership Queries. 611-620
Electronic Edition (link) BibTeX
Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. 621-630
Electronic Edition (link) BibTeX