45. FOCS 2004: Rome, Italy

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 NC⁰. 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 Õ(n²) 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
  

Last update Wed May 22 23:33:05 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page