37. STOC 2005: Baltimore, MD, USA

Session 1A

• Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson:
  Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. 1-10
  
• Ran Raz:
  Extractors with weak random seeds. 11-20
  
• Andrej Bogdanov:
  Pseudorandom generators for low degree polynomials. 21-30
  
• Luca Trevisan:
  On uniform amplification of hardness in NP. 31-38
  

Session 1B

• Patrick Briest, Piotr Krysta, Berthold Vöcking:
  Approximation techniques for utilitarian mechanism design. 39-48
  
• Christos H. Papadimitriou:
  Computing correlated equilibria in multi-player games. 49-56
  
• Baruch Awerbuch, Yossi Azar, Amir Epstein:
  Large the price of routing unsplittable flow. 57-66
  
• George Christodoulou, Elias Koutsoupias:
  The price of anarchy of finite congestion games. 67-73
  
• Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan:
  Market equilibrium via the excess demand function. 74-83
  

Session 2A

• Oded Regev:
  On lattices, learning with errors, random linear codes, and cryptography. 84-93
  
• Miklós Ajtai:
  Representing hard lattices with O(n log n) bits. 94-103
  

Session 2B

• Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu:
  On dynamic range reporting in one dimension. 104-111
  
• Mikkel Thorup:
  Worst-case update times for fully-dynamic all-pairs shortest paths. 112-119
  

Keynote

• Lance Fortnow:
  Beyond NP: the work and legacy of Larry Stockmeyer. 120-127
  

Session 4A

• Noga Alon, Asaf Shapira:
  Every monotone graph property is testable. 128-137
  
• Eldar Fischer, Ilan Newman:
  Testing versus estimation of graph properties. 138-146
  
• Ronitt Rubinfeld, Rocco A. Servedio:
  Testing monotone high-dimensional distributions. 147-156
  
• Katalin Friedl, Gábor Ivanyos, Miklos Santha:
  Efficient testing of groups. 157-166
  

Session 4B

• Joseph Cheriyan, Adrian Vetta:
  Approximation algorithms for network design with metric costs. 167-175
  
• Moses Charikar, Adriana Karagiozova:
  On non-uniform multicommodity buy-at-bulk network design. 176-182
  
• Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
  Multicommodity flow, well-linked terminals, and routing problems. 183-192
  
• Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke:
  Oblivious routing in directed graphs with random demands. 193-201
  

Session 5A

• Piotr Indyk, David P. Woodruff:
  Optimal approximations of the frequency moments of data streams. 202-208
  
• Gereon Frahling, Christian Sohler:
  Coresets in dynamic geometric data streams. 209-217
  
• Rafail Ostrovsky, Yuval Rabani:
  Low distortion embeddings for edit distance. 218-224
  
• Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos:
  Low-distortion embeddings of general metrics into the line. 225-233
  

Session 5B

• Mikolaj Bojanczyk, Thomas Colcombet:
  Tree-walking automata do not recognize all regular languages. 234-243
  
• Itai Benjamini, Oded Schramm, David Bruce Wilson:
  Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. 244-250
  
• Michael Alekhnovich:
  Lower bounds for k-DNF resolution on random 3-CNFs. 251-256
  
• Michal Koucký, Pavel Pudlák, Denis Thérien:
  Bounded-depth circuits: separating wires from gates. 257-265
  

Session 6A

• Eli Ben-Sasson, Madhu Sudan:
  Simple PCPs with poly-log rate and query complexity. 266-275
  
• Matthew Andrews, Lisa Zhang:
  Hardness of the undirected edge-disjoint paths problem. 276-283
  
• Matthew Andrews, Lisa Zhang:
  Hardness of the undirected congestion minimization problem. 284-293
  
• Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
  Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. 294-303
  

Session 6B

• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  Computing the first Betti number and the connected components of semi-algebraic sets. 304-312
  
• Saugata Basu:
  Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. 313-322
  
• Xi Chen, Xiaotie Deng:
  On algorithms for discrete and approximate brouwer fixed points. 323-330
  
• Yossi Azar, Amir Epstein:
  Convex programming for scheduling unrelated parallel machines. 331-337
  

Session 7A

• Saurabh Sanghvi, Salil P. Vadhan:
  The round complexity of two-party random selection. 338-347
  
• Lance Fortnow, Rahul Santhanam, Luca Trevisan:
  Hierarchies for semantic classes. 348-355
  

Session 7B

• Haim Kaplan, Eyal Kushilevitz, Yishay Mansour:
  Learning with attribute costs. 356-365
  
• Elchanan Mossel, Sébastien Roch:
  Learning nonsingular phylogenies and hidden Markov models. 366-375
  

Best Paper

• Omer Reingold:
  Undirected ST-connectivity in log-space. 376-385
  

Session 9A

• Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram:
  Universal approximations for TSP, Steiner tree, and set cover. 386-395
  
• Naveen Garg:
  Saving an epsilon: a 2-approximation for the k-MST problem in graphs. 396-402
  
• Ben Morris:
  The mixing time of the Thorp shuffle. 403-412
  
• Mary Cryan, Martin E. Dyer, Dana Randall:
  Approximately counting integral flows and cell-bounded contingency tables. 413-422
  

Session 9B

• Van H. Vu:
  Spectral norm of random matrices. 423-430
  
• Terence Tao, Van H. Vu:
  On random pm 1 matrices: singularity and determinant. 431-440
  
• Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera:
  On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. 441-449
  
• Micah Adler, Jeff Edmonds, Jirí Matousek:
  Towards asymptotic optimality in probabilistic packet marking. 450-459
  

Session 10A

• Yaoyun Shi:
  Tensor norms and the classical communication complexity of nonlocal quantum measurement. 460-467
  
• Sean Hallgren:
  Fast quantum algorithms for computing the unit group and class group of a number field. 468-474
  
• Arthur Schmidt, Ulrich Vollmer:
  Polynomial time quantum algorithm for the computation of the unit group of a number field. 475-480
  
• Michael Ben-Or, Avinatan Hassidim:
  Fast quantum byzantine agreement. 481-485
  

Session 10B

• Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor:
  Quadratic forms on graphs. 486-493
  
• Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
  Lower-stretch spanning trees. 494-503
  
• Daniel Gonçalves:
  Edge partition of planar sraphs into two outerplanar graphs. 504-512
  

Session 11A

• Luis von Ahn, Nicholas J. Hopper, John Langford:
  Covert two-party computation. 513-522
  
• Hoeteck Wee:
  On obfuscating point functions. 523-532
  
• Rafael Pass, Alon Rosen:
  New and improved constructions of non-malleable cryptographic protocols. 533-542
  
• Matt Lepinski, Silvio Micali, Abhi Shelat:
  Collusion-free protocols. 543-552
  

Session 11B

• Sanjeev Arora, James R. Lee, Assaf Naor:
  Euclidean distortion and the sparsest cut. 553-562
  
• Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee:
  Improved approximation algorithms for minimum-weight vertex separators. 563-572
  
• Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev:
  O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. 573-581
  
• Joseph Naor, Roy Schwartz:
  Balanced metric labeling. 582-591
  

Session 12A

• Zeev Dvir, Amir Shpilka:
  Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. 592-601
  
• Venkatesan Guruswami, Atri Rudra:
  Limits to list decoding Reed-Solomon codes. 602-609
  

Session 12B

• Shahar Dobzinski, Noam Nisan, Michael Schapira:
  Approximation algorithms for combinatorial auctions with complement-free bidders. 610-618
  
• Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan:
  Derandomization of auctions. 619-625
  

Best Student Paper

• Vladimir Trifonov:
  An O(log n log log n) space algorithm for undirected st-connectivity. 626-633
  

Session 14A

• Scott Aaronson:
  The complexity of agreement. 634-643
  
• Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran:
  Concurrent general composition of secure protocols in the timing model. 644-653
  
• Yevgeniy Dodis, Adam Smith:
  Correcting errors without leaking partial information. 654-663
  
• Thomas Holenstein:
  Key agreement from weak bit agreement. 664-673
  

Session 14B

• Ferdinando Cicalese, Eduardo Sany Laber:
  A new strategy for querying priced information. 674-683
  
• Nir Ailon, Moses Charikar, Alantha Newman:
  Aggregating inconsistent information: ranking and clustering. 684-693
  
• Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore:
  On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. 694-703
  
• Christian Scheideler:
  How to spread adversarial nodes?: rotate! 704-713
  

Session 15A

• Eli Gafni, Rachid Guerraoui, Bastian Pochon:
  From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. 714-722
  
• Prasad Jayanti:
  An optimal multi-writer snapshot algorithm. 723-732
  
• Bogdan S. Chlebus, Dariusz R. Kowalski:
  Cooperative asynchronous update of shared memory. 733-739
  

Session 15B

• Johan Håstad:
  Every 2-CSP allows nontrivial approximation. 740-746
  
• Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala:
  Tensor decomposition and approximation schemes for constraint satisfaction problems. 747-754
  
• Klaus Jansen, Rob van Stee:
  On strip packing With rotations. 755-761
  

Last update Fri May 25 08:42:22 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page