35. STOC 2003: San Diego, California, USA

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA. ACM 2003, ISBN 1-58113-674-9 BibTeX

@proceedings{DBLP:conf/stoc/2003,
  title     = {Proceedings of the 35th Annual ACM Symposium on Theory of Computing,
               June 9-11, 2003, San Diego, CA, USA},
  booktitle = {STOC},
  publisher = {ACM},
  year      = {2003},
  isbn      = {1-58113-674-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Session 1A

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen:
Hidden translation and orbit coset in quantum computing. 1-9
Electronic Edition (ACM DL) BibTeX
Leonid Gurvits:
Classical deterministic complexity of Edmonds' Problem and quantum entanglement. 10-19
Electronic Edition (ACM DL) BibTeX
Dorit Aharonov, Amnon Ta-Shma:
Adiabatic quantum state generation and statistical zero knowledge. 20-29
Electronic Edition (ACM DL) BibTeX

Session 1B

Moses Charikar, Liadan O'Callaghan, Rina Panigrahy:
Better streaming algorithms for clustering problems. 30-39
Electronic Edition (ACM DL) BibTeX
C. Greg Plaxton:
Approximation algorithms for hierarchical location problems. 40-49
Electronic Edition (ACM DL) BibTeX
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani:
Approximation schemes for clustering problems. 50-58
Electronic Edition (ACM DL) BibTeX

Session 2A

Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman:
Exponential algorithmic speedup by a quantum walk. 59-68
Electronic Edition (ACM DL) BibTeX
Hartmut Klauck:
Quantum time-space tradeoffs for sorting. 69-76
Electronic Edition (ACM DL) BibTeX
Andrew Chi-Chih Ya:
On the power of quantum fingerprinting. 77-81
Electronic Edition (ACM DL) BibTeX

Session 2B

Yossi Azar, Yossi Richter:
Management of multi-queue switches in QoS networks. 82-89
Electronic Edition (ACM DL) BibTeX
Eyal Amir, Robert Krauthgamer, Satish Rao:
Constant factor approximation of vertex-cuts in planar graphs. 90-99
Electronic Edition (ACM DL) BibTeX
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
The online set cover problem. 100-105
Electronic Edition (ACM DL) BibTeX

Session 3A

Iordanis Kerenidis, Ronald de Wolf:
Exponential lower bound for 2-query locally decodable codes via a quantum argument. 106-115
Electronic Edition (ACM DL) BibTeX
Gábor Tardos:
Optimal probabilistic fingerprint codes. 116-125
Electronic Edition (ACM DL) BibTeX
Venkatesan Guruswami, Piotr Indyk:
Linear time encodable and list decodable codes. 126-135
Electronic Edition (ACM DL) BibTeX
Don Coppersmith, Madhu Sudan:
Reconstructing curves in three (and higher) dimensional space from noisy data. 136-142
Electronic Edition (ACM DL) BibTeX

Session 3B

Lukasz Kowalik, Maciej Kurowski:
Short path queries in planar graphs in constant time. 143-148
Electronic Edition (ACM DL) BibTeX
Mikkel Thorup:
Integer priority queues with decrease key in constant time and the single source shortest paths problem. 149-158
Electronic Edition (ACM DL) BibTeX
Camil Demetrescu, Giuseppe F. Italiano:
A new approach to dynamic all pairs shortest paths. 159-166
Electronic Edition (ACM DL) BibTeX
Richard Cole, Ramesh Hariharan:
A fast algorithm for computing steiner edge connectivity. 167-176
Electronic Edition (ACM DL) BibTeX

Session 4A

Robert Rettinger, Klaus Weihrauch:
The computational complexity of some julia sets. 177-185
Electronic Edition (ACM DL) BibTeX
Martin Sauerhoff, Philipp Woelfel:
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. 186-195
Electronic Edition (ACM DL) BibTeX

Session 4B

Adam Kalai, Rocco A. Servedio:
Boosting in the presence of noise. 195-205
Electronic Edition (ACM DL) BibTeX
Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning juntas. 206-212
Electronic Edition (ACM DL) BibTeX

Session 5A

Jeong Han Kim, Van H. Vu:
Generating random regular graphs. 213-222
Electronic Edition (ACM DL) BibTeX
Dimitris Achlioptas, Yuval Peres:
The threshold for random k-SAT is 2^k (ln 2 - O(k)). 223-231
Electronic Edition (ACM DL) BibTeX
René Beier, Berthold Vöcking:
Random knapsack in expected polynomial time. 232-241
Electronic Edition (ACM DL) BibTeX

Session 5B

Nikhil Bansal, Kirk Pruhs:
Server scheduling in the L_p norm: a rising tide lifts all boat. 242-250
Electronic Edition (ACM DL) BibTeX
Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman:
Work-competitive scheduling for cooperative computing with dynamic groups. 251-258
Electronic Edition (ACM DL) BibTeX
Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert:
A tight time lower bound for space-optimal implementations of multi-writer snapshots. 259-268
Electronic Edition (ACM DL) BibTeX

Session 6A

Thomas P. Hayes:
Randomly coloring graphs of girth at least five. 269-278
Electronic Edition (ACM DL) BibTeX
Ben Morris, Yuval Peres:
Evolving sets and mixin. 279-286
Electronic Edition (ACM DL) BibTeX
Sergey Bobkov, Prasad Tetali:
Modified log-sobolev inequalities, mixing and hypercontractivity. 287-296
Electronic Edition (ACM DL) BibTeX

Session 6B

Anna C. Gilbert, Howard J. Karloff:
On the fractal behavior of TCP. 297-306
Electronic Edition (ACM DL) BibTeX
Gerth Stølting Brodal, Rolf Fagerberg:
On the limits of cache-obliviousness. 307-315
Electronic Edition (ACM DL) BibTeX
Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami:
A sublinear algorithm for weakly approximating edit distance. 316-324
Electronic Edition (ACM DL) BibTeX

Session 7A

Ryan O'Donnell, Rocco A. Servedio:
New degree bounds for polynomial threshold functions. 325-334
Electronic Edition (ACM DL) BibTeX
Ziv Bar-Yossef:
Sampling lower bounds via information theory. 335-344
Electronic Edition (ACM DL) BibTeX
Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
Some 3CNF properties are hard to test. 345-354
Electronic Edition (ACM DL) BibTeX
Valentine Kabanets, Russell Impagliazzo:
Derandomizing polynomial identity tests means proving circuit lower bounds. 355-364
Electronic Edition (ACM DL) BibTeX

Session 7B

Anupam Gupta, Amit Kumar, Tim Roughgarden:
Simpler and better approximation algorithms for network design. 365-372
Electronic Edition (ACM DL) BibTeX
Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram:
Meet and merge: approximation algorithms for confluent flows. 373-382
Electronic Edition (ACM DL) BibTeX
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke:
Optimal oblivious routing in polynomial time. 383-388
Electronic Edition (ACM DL) BibTeX
Jochen Könemann, R. Ravi:
Primal-dual meets local search: approximating MST's with nonuniform degree bounds. 389-395
Electronic Edition (ACM DL) BibTeX

Session 8A

Miklós Ajtai:
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. 396-406
Electronic Edition (ACM DL) BibTeX
Oded Regev:
New lattice based cryptographic constructions. 407-416
Electronic Edition (ACM DL) BibTeX
Rosario Gennaro, Yael Gertner, Jonathan Katz:
Lower bounds on the efficiency of encryption and digital signature schemes. 417-425
Electronic Edition (ACM DL) BibTeX
Ivan Damgård, Jens Groth:
Non-interactive and reusable non-malleable commitment schemes. 426-437
Electronic Edition (ACM DL) BibTeX

Session 8B

Robert Krauthgamer, James R. Lee:
The intrinsic dimensionality of graphs. 438-447
Electronic Edition (ACM DL) BibTeX
Jittat Fakcharoenphol, Satish Rao, Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics. 448-455
Electronic Edition (ACM DL) BibTeX
Yuri Rabinovich:
On average distortion of embedding metrics into the line and into L1. 456-462
Electronic Edition (ACM DL) BibTeX
Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
On metric ramsey-type phenomena. 463-472
Electronic Edition (ACM DL) BibTeX

Session 9A

Moshe Dror, Alon Efrat, Anna Lubiw, Joseph S. B. Mitchell:
Touring a sequence of polygons. 473-482
Electronic Edition (ACM DL) BibTeX
Jie Gao, Li Zhang:
Well-separated pair decomposition for the unit-disk graph metric and its applications. 483-492
Electronic Edition (ACM DL) BibTeX
Tamal K. Dey, Joachim Giesen, Matthias John:
Alpha-shapes and flow shapes are homotopy equivalent. 493-502
Electronic Edition (ACM DL) BibTeX

Session 9B

Baruch Awerbuch, Yossi Azar, Adam Meyerson:
Reducing truth-telling online mechanisms to online optimization. 503-510
Electronic Edition (ACM DL) BibTeX
Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, Tom Wexler:
Near-optimal network design with selfish agents. 511-520
Electronic Edition (ACM DL) BibTeX
Richard Cole, Yevgeniy Dodis, Tim Roughgarden:
Pricing network edges for heterogeneous selfish users. 521-530
Electronic Edition (ACM DL) BibTeX

Session 10A

Bernard Chazelle, Ding Liu, Avner Magen:
Sublinear geometric algorithms. 531-540
Electronic Edition (ACM DL) BibTeX
Boris Aronov, János Pach, Micha Sharir, Gábor Tardos:
Distinct distances in three and higher dimensions. 541-546
Electronic Edition (ACM DL) BibTeX
Boris Aronov, Vladlen Koltun, Micha Sharir:
Cutting triangular cycles of lines in space. 547-555
Electronic Edition (ACM DL) BibTeX

Session 10B

Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup:
OPT versus LOAD in dynamic storage allocation. 556-564
Electronic Edition (ACM DL) BibTeX
Robert D. Kleinberg, Frank Thomson Leighton:
Consistent load balancing via spread minimization. 565-574
Electronic Edition (ACM DL) BibTeX
Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani:
A stochastic process on the hypercube with applications to peer-to-peer networks. 575-584
Electronic Edition (ACM DL) BibTeX

Session 11A

Eran Halperin, Robert Krauthgamer:
Polylogarithmic inapproximability. 585-594
Electronic Edition (ACM DL) BibTeX
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover. 595-601
Electronic Edition (ACM DL) BibTeX
Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson:
Extractors: optimal up to constant factors. 602-611
Electronic Edition (ACM DL) BibTeX
Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson:
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. 612-621
Electronic Edition (ACM DL) BibTeX

Session 11B

Anna Östlin, Rasmus Pagh:
Uniform hashing in constant time and linear space. 622-628
Electronic Edition (ACM DL) BibTeX
Martin Dietzfelbinger, Philipp Woelfel:
Almost random graphs with simple hash functions. 629-638
Electronic Edition (ACM DL) BibTeX
Haim Kaplan, Eyal Molad, Robert Endre Tarjan:
Dynamic rectangular intersection with priorities. 639-648
Electronic Edition (ACM DL) BibTeX
Mikkel Thorup:
Space efficient dynamic stabbing with fast queries. 649-658
Electronic Edition (ACM DL) BibTeX

Session 12A

Anna Gál, Adi Rosén:
Lower bounds on the amount of randomness in private computation. 659-666
Electronic Edition (ACM DL) BibTeX
T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani:
Cell-probe lower bounds for the partial match problem. 667-672
Electronic Edition (ACM DL) BibTeX
T. S. Jayram, Ravi Kumar, D. Sivakumar:
Two applications of information complexity. 673-682
Electronic Edition (ACM DL) BibTeX
Yehuda Lindell:
Bounded-concurrent secure two-party computation without setup assumptions. 683-692
Electronic Edition (ACM DL) BibTeX

Session 12B

Martin E. Dyer:
Approximate counting by dynamic programming. 693-699
Electronic Edition (ACM DL) BibTeX
Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. 700-709
Electronic Edition (ACM DL) BibTeX
Toshiya Itoh, Yoshinori Takei, Jun Tarui:
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. 710-719
Electronic Edition (ACM DL) BibTeX
Joel Friedman:
A proof of Alon's second eigenvalue conjecture. 720-724
Electronic Edition (ACM DL) BibTeX