- 2004
- Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl:
On the Streaming Model Augmented with a Sorting Primitive. FOCS 2004: 540-549 - Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. FOCS 2004: 42-51 - Dorit Aharonov, Oded Regev:
Lattice Problems in NP cap coNP. FOCS 2004: 362-371 - Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. FOCS 2004: 621-630 - Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. FOCS 2004: 22-31 - Matthew Andrews:
Hardness of Buy-at-Bulk Network Design. FOCS 2004: 115-124 - Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
The Price of Stability for Network Design with Fair Cost Allocation. FOCS 2004: 295-304 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Cryptography in NC0. FOCS 2004: 166-175 - Sanjeev Arora, Elad Hazan, Satyen Kale:
0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time. FOCS 2004: 238-247 - John Augustine, Sandy Irani, Chaitanya Swamy:
Optimal Power-Down Strategies. FOCS 2004: 530-539 - Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
Dynamic Speed Scaling to Manage Energy and Temperature. FOCS 2004: 520-529 - Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
Approximating Edit Distance Efficiently. FOCS 2004: 550-559 - Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass:
Universally Composable Protocols with Relaxed Set-Up Assumptions. FOCS 2004: 186-195 - Boaz Barak, Russell Impagliazzo
, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. FOCS 2004: 384-393 - Yonatan Bilu, Nathan Linial:
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. FOCS 2004: 404-412 - Laurence Bisht, Nader H. Bshouty, Lawrance Khoury:
Learning with Errors in Answers to Membership Queries. FOCS 2004: 611-620 - Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. FOCS 2004: 473-482 - Moses Charikar, Michel X. Goemans, Howard J. Karloff:
On the Integrality Ratio for Asymmetric TSP. FOCS 2004: 101-107 - Moses Charikar, Anthony Wirth:
Maximizing Quadratic Programs: Extending Grothendieck's Inequality. FOCS 2004: 54-60 - Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs. FOCS 2004: 71-80 - Qi Cheng, Daqing Wan:
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). FOCS 2004: 335-341 - Steve Chien, Alistair Sinclair:
Algebras with Polynomial Identities and Computing the Determinant. FOCS 2004: 352-361 - Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Machine Minimization for Scheduling Jobs with Interval Constraints. FOCS 2004: 81-90 - Julia Chuzhoy, Joseph Naor:
The Hardness of Metric Labeling. FOCS 2004: 108-114 - Harold S. Connamacher, Michael Molloy:
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem. FOCS 2004: 590-599 - Anirban Dasgupta, John E. Hopcroft, Frank McSherry:
Spectral Analysis of Random Graphs with Skewed Degree Distributions. FOCS 2004: 602-610 - Brian C. Dean, Michel X. Goemans, Jan Vondrák:
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. FOCS 2004: 208-217 - Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. FOCS 2004: 484-490 - Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. FOCS 2004: 155-164 - Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai:
On the (Im)possibility of Cryptography with Imperfect Randomness. FOCS 2004: 196-205
