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
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
- Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor: Machine Minimization for Scheduling Jobs with Interval Constraints. 81-90
Session 3
- Moses Charikar, Michel X. Goemans, Howard J. Karloff: On the Integrality Ratio for Asymmetric TSP. 101-107
- 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
- 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
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
- 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
- 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
- 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
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team