default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID45th FOCS 2004: Rome, Italy
- 45th Symposium on Foundations of Computer Science, FOCS 2004, Rome, Italy, October 17-19, 2004, Proceedings. IEEE Computer Society 2004, ISBN 0-7695-2228-9
Session 1
- Carlos Mochon:
Quantum Weak Coin-Flipping with Bias of 0.192. 2-11 - Hartmut Klauck, Robert Spalek, Ronald de Wolf:
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. 12-21 - Andris Ambainis:
Quantum Walk Algorithm for Element Distinctness. 22-31 - Mario Szegedy:
Quantum Speed-Up of Markov Chain Based Algorithms. 32-41 - Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev:
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. 42-51
Session 2
- Moses Charikar
, Anthony Wirth:
Maximizing Quadratic Programs: Extending Grothendieck's Inequality. 54-60 - Lap Chi Lau:
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. 61-70 - Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
Edge-Disjoint Paths in Planar Graphs. 71-80 - Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor:
Machine Minimization for Scheduling Jobs with Interval Constraints. 81-90
Session 3
- Jirí Matousek, Tibor Szabó:
Random Edge Can Be Exponential on Abstract Cubes. 92-100 - Moses Charikar, Michel X. Goemans, Howard J. Karloff:
On the Integrality Ratio for Asymmetric TSP. 101-107 - Julia Chuzhoy, Joseph Naor:
The Hardness of Metric Labeling. 108-114 - Matthew Andrews:
Hardness of Buy-at-Bulk Network Design. 115-124
Session 4
- Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in Lattices. 126-135 - Subhash Khot:
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. 136-145 - Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell:
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? 146-154 - Irit Dinur, Omer Reingold:
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. 155-164
Session 5
- Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Cryptography in NC0. 166-175 - Salil P. Vadhan:
An Unconditional Study of Computational Zero Knowledge. 176-185 - Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass:
Universally Composable Protocols with Relaxed Set-Up Assumptions. 186-195 - Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai:
On the (Im)possibility of Cryptography with Imperfect Randomness. 196-205
Session 6
- Brian C. Dean, Michel X. Goemans, Jan Vondrák:
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. 208-217 - Anupam Gupta, R. Ravi, Amitabh Sinha:
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. 218-227 - David B. Shmoys, Chaitanya Swamy:
Stochastic Optimization is (Almost) as easy as Deterministic Optimization. 228-237 - Sanjeev Arora, Elad Hazan, Satyen Kale:
0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time. 238-247 - Marcin Mucha, Piotr Sankowski:
Maximum Matchings via Gaussian Elimination. 248-255
Session 7
- Rahul Savani, Bernhard von Stengel:
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. 258-267 - George Karakostas, Stavros G. Kolliopoulos:
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. 268-276 - Lisa Fleischer, Kamal Jain, Mohammad Mahdian:
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. 277-285 - Kamal Jain:
A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. 286-294 - 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
Session 8
- Leslie G. Valiant:
Holographic Algorithms (Extended Abstract). 306-315 - Lance Fortnow, Rahul Santhanam:
Hierarchy Theorems for Probabilistic Polynomial Time. 316-324 - Michael Langberg:
Private Codes or Succinct Random Codes That Are (Almost) Perfect. 325-334 - Qi Cheng, Daqing Wan:
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). 335-341
Session 9
- Ran Raz:
Multilinear-NC neq Multilinear-NC. 344-351 - Steve Chien, Alistair Sinclair:
Algebras with Polynomial Identities and Computing the Determinant. 352-361 - Dorit Aharonov, Oded Regev:
Lattice Problems in NP cap coNP. 362-371 - Daniele Micciancio, Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures. 372-381
Session 10
- Boaz Barak, Russell Impagliazzo, Avi Wigderson:
Extracting Randomness Using Few Independent Sources. 384-393 - Ariel Gabizon, Ran Raz, Ronen Shaltiel:
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. 394-403 - Yonatan Bilu, Nathan Linial:
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. 404-412 - Tali Kaufman, Dana Ron:
Testing Polynomials over General Fields. 413-422 - Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman:
Testing Low-Degree Polynomials over Prime Fields. 423-432
Session 11
- Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor:
Measured Descent: A New Embedding Method for Finite Metrics. 434-443 - Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler:
Triangulation and Embedding Using Small Sets of Beacons. 444-453 - Amit Kumar, Yogish Sabharwal, Sandeep Sen:
A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions. 454-462 - Nir Halman:
On the Power of Discrete and of Lexicographic Helly-Type Theorems. 463-472 - Amit Chakrabarti, Oded Regev:
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. 473-482
Session 12
- Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu:
Dynamic Optimality - Almost. 484-490 - Gianni Franceschini, Roberto Grossi:
No Sorting? Better Searching! 491-498 - Liam Roditty, Uri Zwick:
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. 499-508 - Piotr Sankowski:
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). 509-517
Session 13
- Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs:
Dynamic Speed Scaling to Manage Energy and Temperature. 520-529 - John Augustine, Sandy Irani, Chaitanya Swamy:
Optimal Power-Down Strategies. 530-539 - Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl:
On the Streaming Model Augmented with a Sorting Primitive. 540-549 - Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar:
Approximating Edit Distance Efficiently. 550-559
Session 14
- Leslie Ann Goldberg, Russell A. Martin, Mike Paterson:
trong Spatial Mixing for Lattice Graphs with Fewer Colours. 562-571 - Elchanan Mossel, Yuval Peres, Alistair Sinclair:
Shuffling by Semi-Random Transpositions. 572-581 - Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda:
Randomly Coloring Constant Degree Graphs. 582-589 - Harold S. Connamacher, Michael Molloy:
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem. 590-599
Session 15
- Anirban Dasgupta, John E. Hopcroft, Frank McSherry:
Spectral Analysis of Random Graphs with Skewed Degree Distributions. 602-610 - Laurence Bisht, Nader H. Bshouty, Lawrance Khoury:
Learning with Errors in Answers to Membership Queries. 611-620 - Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. 621-630
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-05 22:23 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
