31st STOC 1999: Atlanta, Georgia, USA
- Jeffrey Scott Vitter, Lawrence L. Larmore, Frank Thomson Leighton:
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA. ACM 1999, ISBN 1-58113-067-8 - Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys:
A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). 1-10 - Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis:
Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. 19-28 - Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. 29-40 - Yuval Ishai, Eyal Kushilevitz:
Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). 79-88 - Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin:
One-Way Functions Are Essential for Single-Server Private Information Retrieval. 89-98 - Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
On targeting Markov segments. 99-108 - Edith Cohen, Haim Kaplan:
Exploiting Regularities in Web Traffic Patterns for Cache Replacement. 109-118 - Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, Hsing-Kuo Wong:
Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. 119-128 - Luca Trevisan:
Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). 141-148 - Ran Raz, Omer Reingold, Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. 149-158 - Giovanni Di Crescenzo, Russell Impagliazzo:
Security-Preserving Hardness-Amplification for Any Regular One-Way Function. 169-178 - Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, Éva Tardos:
Scheduling Data Transfers in a Network and the Set Scheduling Problem. 189-197 - Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev:
Minimizing the Flow Time Without Migration. 198-205 - David Gamarnik:
Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. 206-214 - Christian Scheideler, Berthold Vöcking:
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. 215-224 - Vadim Olshevsky, Mohammad Amin Shokrollahi:
A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. 235-244 - Ran Canetti, Rafail Ostrovsky:
Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). 255-264 - Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum:
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). 265-274 - Leonard J. Schulman, Vijay V. Vazirani:
Majorizing Estimators and the Approximation of #P-Complete Problems. 288-294 - Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov:
A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. 305-311 - Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. 312-321 - Leonard J. Schulman, Umesh V. Vazirani:
Molecular Scale Heat Engines and Scalable Quantum Computation. 322-329 - Alexander Russell, Michael E. Saks, David Zuckerman:
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 339-347 - Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. 376-383 - Ashwin Nayak, Felix Wu:
The Quantum Query Complexity of Approximating the Median and Related Statistics. 384-393 - Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko:
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. 394-399 - Martin Skutella, Gerhard J. Woeginger:
A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. 400-407 - Klaus Jansen, Lorant Porkolab:
Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. 408-417 - Jianer Chen, Antonio Miranda:
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). 418-427 - Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. 435-444 - S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel:
Compact Grid Layouts of Multi-Level Networks. 455-463 - Tomás Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani:
Complexity of Graph Partition Problems. 464-472 - Paolo Ferragina, S. Muthukrishnan, Mark de Berg:
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. 483-491 - Valerie King, Garry Sagert:
A Fully Dynamic Algorithm for Maintaining the Transitive Closure. 492-498 - Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe:
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). 499-506 - J. Maurice Rojas:
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). 527-536 - Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract). 537-546 - Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. 547-556 - Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber:
Efficient Recovery from Power Outage (Extended Abstract). 574-582 - Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. 602-611 - Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. 622-631 - Adam R. Klivans, Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. 659-667 - David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young:
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. 668-678 - Uri Zwick:
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. 679-687 - Johannes Blömer, Jean-Pierre Seifert:
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. 711-720 - Jin-yi Cai, Ajay Nerurkar, D. Sivakumar:
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. 726-735