default search action
35th STOC 2003: San Diego, California, USA
- Lawrence L. Larmore, Michel X. Goemans:
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
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 - Leonid Gurvits:
Classical deterministic complexity of Edmonds' Problem and quantum entanglement. 10-19 - Dorit Aharonov, Amnon Ta-Shma
:
Adiabatic quantum state generation and statistical zero knowledge. 20-29
Session 1B
- Moses Charikar
Better streaming algorithms for clustering problems. 30-39 - C. Greg Plaxton:
Approximation algorithms for hierarchical location problems. 40-49 - Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
Approximation schemes for clustering problems. 50-58
Session 2A
- Andrew M. Childs
Exponential algorithmic speedup by a quantum walk. 59-68 - Hartmut Klauck:
Quantum time-space tradeoffs for sorting. 69-76 - Andrew Chi-Chih Yao:
On the power of quantum fingerprinting. 77-81
Session 2B
- Yossi Azar, Yossi Richter:
Management of multi-queue switches in QoS networks. 82-89 - Eyal Amir, Robert Krauthgamer
Constant factor approximation of vertex-cuts in planar graphs. 90-99 - Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor:
The online set cover problem. 100-105
Session 3A
- Iordanis Kerenidis, Ronald de Wolf:
Exponential lower bound for 2-query locally decodable codes via a quantum argument. 106-115 - Gábor Tardos:
Optimal probabilistic fingerprint codes. 116-125 - Venkatesan Guruswami, Piotr Indyk:
Linear time encodable and list decodable codes. 126-135 - Don Coppersmith, Madhu Sudan:
Reconstructing curves in three (and higher) dimensional space from noisy data. 136-142
Session 3B
- Lukasz Kowalik, Maciej Kurowski:
Short path queries in planar graphs in constant time. 143-148 - Mikkel Thorup
Integer priority queues with decrease key in constant time and the single source shortest paths problem. 149-158 - Camil Demetrescu, Giuseppe F. Italiano:
A new approach to dynamic all pairs shortest paths. 159-166 - Richard Cole, Ramesh Hariharan:
A fast algorithm for computing steiner edge connectivity. 167-176
Session 4A
- Robert Rettinger, Klaus Weihrauch:
The computational complexity of some julia sets. 177-185 - Martin Sauerhoff, Philipp Woelfel:
Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. 186-195
Session 4B
- Adam Kalai, Rocco A. Servedio:
Boosting in the presence of noise. 195-205 - Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning juntas. 206-212
Session 5A
- Jeong Han Kim, Van H. Vu:
Generating random regular graphs. 213-222 - Dimitris Achlioptas, Yuval Peres:
The threshold for random k-SAT is 2k (ln 2 - O(k)). 223-231 - René Beier, Berthold Vöcking:
Random knapsack in expected polynomial time. 232-241
Session 5B
- Nikhil Bansal, Kirk Pruhs:
Server scheduling in the Lp norm: a rising tide lifts all boat. 242-250 - Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman
Work-competitive scheduling for cooperative computing with dynamic groups. 251-258 - Panagiota Fatourou, Faith E. Fich, Eric Ruppert:
A tight time lower bound for space-optimal implementations of multi-writer snapshots. 259-268
Session 6A
- Thomas P. Hayes:
Randomly coloring graphs of girth at least five. 269-278 - Ben Morris, Yuval Peres:
Evolving sets and mixin. 279-286 - Sergey G. Bobkov, Prasad Tetali:
Modified log-sobolev inequalities, mixing and hypercontractivity. 287-296
Session 6B
- Anna C. Gilbert, Howard J. Karloff:
On the fractal behavior of TCP. 297-306 - Gerth Stølting Brodal
On the limits of cache-obliviousness. 307-315 - 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
Session 7A
- Ryan O'Donnell, Rocco A. Servedio
New degree bounds for polynomial threshold functions. 325-334 - Ziv Bar-Yossef:
Sampling lower bounds via information theory. 335-344 - Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova:
Some 3CNF properties are hard to test. 345-354 - Valentine Kabanets, Russell Impagliazzo
Derandomizing polynomial identity tests means proving circuit lower bounds. 355-364
Session 7B
- Anupam Gupta, Amit Kumar, Tim Roughgarden:
Simpler and better approximation algorithms for network design. 365-372 - Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram:
Meet and merge: approximation algorithms for confluent flows. 373-382 - Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke:
Optimal oblivious routing in polynomial time. 383-388 - Jochen Könemann, R. Ravi:
Primal-dual meets local search: approximating MST's with nonuniform degree bounds. 389-395
Session 8A
- Miklós Ajtai:
The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. 396-406 - Oded Regev:
New lattice based cryptographic constructions. 407-416 - Rosario Gennaro, Yael Gertner, Jonathan Katz:
Lower bounds on the efficiency of encryption and digital signature schemes. 417-425 - Ivan Damgård, Jens Groth:
Non-interactive and reusable non-malleable commitment schemes. 426-437
Session 8B
- Robert Krauthgamer
The intrinsic dimensionality of graphs. 438-447 - Jittat Fakcharoenphol, Satish Rao, Kunal Talwar:
A tight bound on approximating arbitrary metrics by tree metrics. 448-455 - Yuri Rabinovich:
On average distortion of embedding metrics into the line and into L1. 456-462 - Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor:
On metric ramsey-type phenomena. 463-472
Session 9A
- Moshe Dror, Alon Efrat
Touring a sequence of polygons. 473-482 - Jie Gao, Li Zhang:
Well-separated pair decomposition for the unit-disk graph metric and its applications. 483-492 - Tamal K. Dey, Joachim Giesen, Matthias John:
Alpha-shapes and flow shapes are homotopy equivalent. 493-502
Session 9B
- Baruch Awerbuch, Yossi Azar, Adam Meyerson:
Reducing truth-telling online mechanisms to online optimization. 503-510 - Elliot Anshelevich
Near-optimal network design with selfish agents. 511-520 - Richard Cole, Yevgeniy Dodis, Tim Roughgarden:
Pricing network edges for heterogeneous selfish users. 521-530
Session 10A
- Bernard Chazelle, Ding Liu, Avner Magen:
Sublinear geometric algorithms. 531-540 - Boris Aronov, János Pach, Micha Sharir, Gábor Tardos:
Distinct distances in three and higher dimensions. 541-546 - Boris Aronov, Vladlen Koltun, Micha Sharir:
Cutting triangular cycles of lines in space. 547-555
Session 10B
- Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup:
OPT versus LOAD in dynamic storage allocation. 556-564 - Robert D. Kleinberg, Frank Thomson Leighton:
Consistent load balancing via spread minimization. 565-574 - 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
Session 11A
- Eran Halperin, Robert Krauthgamer
Polylogarithmic inapproximability. 585-594 - Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev:
A new multilayered PCP and the hardness of hypergraph vertex cover. 595-601 - Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson:
Extractors: optimal up to constant factors. 602-611 - Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson:
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. 612-621
Session 11B
- Anna Östlin, Rasmus Pagh:
Uniform hashing in constant time and linear space. 622-628 - Martin Dietzfelbinger
Almost random graphs with simple hash functions. 629-638 - Haim Kaplan, Eyal Molad, Robert Endre Tarjan:
Dynamic rectangular intersection with priorities. 639-648 - Mikkel Thorup:
Space efficient dynamic stabbing with fast queries. 649-658
Session 12A
- Anna Gál, Adi Rosén:
Lower bounds on the amount of randomness in private computation. 659-666 - T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani
Cell-probe lower bounds for the partial match problem. 667-672 - T. S. Jayram, Ravi Kumar, D. Sivakumar:
Two applications of information complexity. 673-682 - Yehuda Lindell:
Bounded-concurrent secure two-party computation without setup assumptions. 683-692
Session 12B
- Martin E. Dyer
Approximate counting by dynamic programming. 693-699 - Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. 700-709 - Toshiya Itoh, Yoshinori Takei, Jun Tarui:
On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. 710-719 - Joel Friedman
A proof of Alon's second eigenvalue conjecture. 720-724
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-14 21:08 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: