36. STOC 2004: Chicago, IL, USA

@proceedings{DBLP:conf/stoc/2004,
  editor    = {L{\'a}szl{\'o} Babai},
  title     = {Proceedings of the 36th Annual ACM Symposium on Theory of Computing,
               Chicago, IL, USA, June 13-16, 2004},
  booktitle = {STOC},
  publisher = {ACM},
  year      = {2004},
  isbn      = {1-58113-852-0},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Session 1A

• Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
  Robust pcps of proximity, shorter pcps and applications to coding. 1-10
  
• Jonas Holmerin, Subhash Khot:
  A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. 11-20
  
• Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor:
  Asymmetric k-center is log^* n-hard to approximate. 21-27
  
• Julia Chuzhoy, Joseph Naor:
  New hardness results for congestion minimization and machine scheduling. 28-34
  
• Susanne Albers, Markus Schmidt:
  On the performance of greedy algorithms in packet buffering. 35-44
  

Session 1B

• Baruch Awerbuch, Robert D. Kleinberg:
  Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. 45-53
  
• Gurmeet Singh Manku, Moni Naor, Udi Wieder:
  Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks. 54-63
  
• Yossi Azar, Yossi Richter:
  The zero-one principle for switching networks. 64-71
  

Session 2A

• Noga Alon, Assaf Naor:
  Approximating the cut-norm via Grothendieck's inequality. 72-80
  
• Daniel A. Spielman, Shang-Hua Teng:
  Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. 81-90
  

Session 2B

• Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein:
  Dictionary matching and indexing with errors and don't cares. 91-100
  
• Irene Finocchi, Giuseppe F. Italiano:
  Sorting and searching in the presence of memory faults (without redundancy). 101-110
  
• Andris Ambainis:
  Quantum algorithms a decade after shor. 111
  

Session 4A

• Andrew Chi-Chih Yao:
  Graph entropy and quantum sorting problems. 112-117
  
• Scott Aaronson:
  Multilinear formulas and skepticism of quantum computing. 118-127
  
• Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
  Exponential separation of quantum and classical one-way communication complexity. 128-137
  

Session 4B

• Guy Kortsarz, Zeev Nutov:
  Approximation algorithm for k-node connected subgraphs via critical graphs. 138-145
  
• Daniel Bienstock, Garud Iyengar:
  Solving fractional packing problems in O^ast(1/?) iterations. 146-155
  
• Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
  The all-or-nothing multicommodity flow problem. 156-165
  

Session 5A

• Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson:
  Approximation algorithms for deadline-TSP and vehicle routing with time-windows. 166-174
  
• Artur Czumaj, Christian Sohler:
  Estimating the weight of metric minimum spanning trees in sublinear-time. 175-183
  
• Liam Roditty, Uri Zwick:
  A fully dynamic reachability algorithm for directed graphs with an almost linear update time. 184-191
  

Session 5B

• Alexander Healy, Salil P. Vadhan, Emanuele Viola:
  Using nondeterminism to amplify hardness. 192-201
  
• Rajeev Alur, P. Madhusudan:
  Visibly pushdown languages. 202-211
  
• Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia:
  Linear FPT reductions and computational lower bounds. 212-221
  
• Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
  Expander flows, geometric embeddings and graph partitioning. 222-231
  

Session 7A

• Rafael Pass:
  Bounded-concurrent secure multi-party computation with a dishonest majority. 232-241
  
• Manoj Prabhakaran, Amit Sahai:
  New notions of security: achieving universal composability without trusted setup. 242-251
  
• Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen:
  Completeness in two-party secure computation: a computational view. 252-261
  
• Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
  Batch codes and their applications. 262-271
  

Session 7B

• Claire Kenyon, Yuval Rabani, Alistair Sinclair:
  Low distortion maps between point sets. 272-280
  
• Kunal Talwar:
  Bypassing the embedding: algorithms for low dimensional metrics. 281-290
  
• Sariel Har-Peled, Soham Mazumdar:
  On coresets for k-means and k-median clustering. 291-300
  
• Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter:
  Isotopic implicit surface meshing. 301-309
  

Session 8A

• László Lovász, Santosh Vempala:
  Hit-and-run from a corner. 310-314
  
• John Dunagan, Santosh Vempala:
  A simple polynomial-time rescaling algorithm for solving linear programs. 315-320
  

Session 8B

• Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman:
  Collective asynchronous reading with polylogarithmic worst-case overhead. 321-330
  
• Michael Elkin:
  Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. 331-340
  
• Éva Tardos:
  Network games. 341-342
  

Session 10A

• René Beier, Berthold Vöcking:
  Typical properties of winners and losers in discrete optimization. 343-352
  
• Retsef Levi, Robin Roundy, David B. Shmoys:
  Primal-dual algorithms for deterministic inventory problems. 353-362
  
• Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar:
  Multi-processor scheduling to minimize flow time with epsilon resource augmentation. 363-372
  

Session 10B

• Piotr Indyk:
  Algorithms for dynamic geometric problems over data streams. 373-380
  
• Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld:
  Sublinear algorithms for testing monotone and unimodal distributions. 381-390
  
• Eldar Fischer:
  The difficulty of testing for isomorphism against a graph that is given in advance. 391-397
  

Session 11A

• José R. Correa, Michel X. Goemans:
  An approximate König's theorem for edge-coloring weighted bipartite graphs. 398-406
  
• Harold N. Gabow:
  Finding paths and cycles of superpolylogarithmic length. 407-416
  
• Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha:
  Boosted sampling: approximation algorithms for stochastic optimization. 417-426
  

Session 11B

• Amir Shpilka, Avi Wigderson:
  Derandomizing homomorphism testing in general groups. 427-435
  
• Venkatesan Guruswami:
  Better extractors for better codes? 436-444
  
• Eyal Rozenman, Aner Shalev, Avi Wigderson:
  A new family of Cayley expanders (?). 445-454
  
• Jonathan A. Kelner:
  Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. 455-464
  
• Scott Aaronson:
  Lower bounds for local search by quantum arguments. 465-474
  
• Peter Bürgisser, Felipe Cucker:
  Counting complexity classes for numeric computations II: algebraic and semialgebraic sets. 475-485
  

Session 14A

• Miklós Ajtai:
  A conjecture about polynomial time computable lattice-lattice functions. 486-493
  
• Miklos Santha, Mario Szegedy:
  Quantum and classical query complexities of local search are polynomially related. 494-501
  
• Ben Reichardt:
  The quantum adiabatic optimization algorithm and local minima. 502-510
  
• Rahul Garg, Sanjiv Kapoor:
  Auction algorithms for market equilibrium. 511-518
  

Session 14B

• Nikhil R. Devanur:
  The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. 519-528
  
• Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta:
  (Almost) tight bounds and existence theorems for confluent flows. 529-538
  
• Kenji Obata:
  Approximate max-integral-flow/min-multicut theorems. 539-545
  

Session 15A

• Mihai Patrascu, Erik D. Demaine:
  Lower bounds for dynamic connectivity. 546-553
  
• Nir Ailon, Bernard Chazelle:
  Lower bounds for linear degeneracy testing. 554-560
  

Session 15B

• David Kempe, Frank McSherry:
  A decentralized algorithm for spectral analysis. 561-568
  
• Jon M. Kleinberg, Mark Sandler:
  Using mixture models for collaborative filtering. 569-578
  
• Avi Wigderson:
  Depth through breadth, or why should we attend talks in other areas? 579
  

Session 17A

• Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari:
  Sharp thresholds For monotone properties in random geometric graphs. 580-586
  
• Dimitris Achlioptas, Assaf Naor:
  The two possible values of the chromatic number of a random graph. 587-593
  
• Uriel Feige:
  On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. 594-603
  
• Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar:
  The complexity of pure Nash equilibria. 604-612
  

Session 17B

• Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien:
  Computing Nash equilibria for scheduling on restricted parallel links. 613-622
  
• Joseph Y. Halpern, Vanessa Teague:
  Rational secret sharing and multiparty computation: extended abstract. 623-632
  
• Ran Raz:
  Multi-linear formulas for permanent and determinant are of super-polynomial size. 633-641