31. STOC 1999:
Atlanta,
Georgia,
USA
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing,
May 1-4,
1999,
Atlanta,
Georgia,
USA. ACM,
1999
- Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys:
A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract).
1-10
Electronic Edition (ACM DL) BibTeX
- Kevin D. Wayne:
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow.
11-18
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra:
PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability.
29-40
Electronic Edition (ACM DL) BibTeX
- Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
Fast Approximate PCPs.
41-50
Electronic Edition (ACM DL) BibTeX
- Marcos A. Kiwi, Frédéric Magniez, Miklos Santha:
Approximate Testing with Relative Error.
51-60
Electronic Edition (ACM DL) BibTeX
- Uri Zwick:
All Pairs Lightest Shortest Paths.
61-69
Electronic Edition (ACM DL) BibTeX
- Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan:
Unique Maximum Matching Algorithms.
70-78
Electronic Edition (ACM DL) BibTeX
- Yuval Ishai, Eyal Kushilevitz:
Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract).
79-88
Electronic Edition (ACM DL) BibTeX
- Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin:
One-Way Functions Are Essential for Single-Server Private Information Retrieval.
89-98
Electronic Edition (ACM DL) BibTeX
- Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
On targeting Markov segments.
99-108
Electronic Edition (ACM DL) BibTeX
- Edith Cohen, Haim Kaplan:
Exploiting Regularities in Web Traffic Patterns for Cache Replacement.
109-118
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Noam Nisan, Amir Ronen:
Algorithmic Mechanism Design (Extended Abstract).
129-140
Electronic Edition (ACM DL) BibTeX
- Luca Trevisan:
Construction of Extractors Using Pseudo-Random Generators (Extended Abstract).
141-148
Electronic Edition (ACM DL) BibTeX
- Ran Raz, Omer Reingold, Salil P. Vadhan:
Extracting all the Randomness and Reducing the Error in Trevisan's Extractors.
149-158
Electronic Edition (ACM DL) BibTeX
- Ran Raz, Omer Reingold:
On Recycling the Randomness of States in Space Bounded Computation.
159-168
Electronic Edition (ACM DL) BibTeX
- Giovanni Di Crescenzo, Russell Impagliazzo:
Security-Preserving Hardness-Amplification for Any Regular One-Way Function.
169-178
Electronic Edition (ACM DL) BibTeX
- Jeff Edmonds:
Scheduling in the Dark.
179-188
Electronic Edition (ACM DL) BibTeX
- Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, Éva Tardos:
Scheduling Data Transfers in a Network and the Set Scheduling Problem.
189-197
Electronic Edition (ACM DL) BibTeX
- Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev:
Minimizing the Flow Time Without Migration.
198-205
Electronic Edition (ACM DL) BibTeX
- David Gamarnik:
Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks.
206-214
Electronic Edition (ACM DL) BibTeX
- Christian Scheideler, Berthold Vöcking:
From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols.
215-224
Electronic Edition (ACM DL) BibTeX
- Oded Goldreich, Dana Ron, Madhu Sudan:
Chinese Remaindering with Errors.
225-234
Electronic Edition (ACM DL) BibTeX
- Vadim Olshevsky, Mohammad Amin Shokrollahi:
A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes.
235-244
Electronic Edition (ACM DL) BibTeX
- Moni Naor, Benny Pinkas:
Oblivious Transfer and Polynomial Evaluation.
245-254
Electronic Edition (ACM DL) BibTeX
- Ran Canetti, Rafail Ostrovsky:
Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract).
255-264
Electronic Edition (ACM DL) BibTeX
- Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum:
Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract).
265-274
Electronic Edition (ACM DL) BibTeX
- Fang Chen, László Lovász, Igor Pak:
Lifting Markov Chains to Speed up Mixing.
275-281
Electronic Edition (ACM DL) BibTeX
- László Lovász, Ravi Kannan:
Faster Mixing via Average Conductance.
282-287
Electronic Edition (ACM DL) BibTeX
- Leonard J. Schulman, Vijay V. Vazirani:
Majorizing Estimators and the Approximation of #P-Complete Problems.
288-294
Electronic Edition (ACM DL) BibTeX
- Paul Beame, Faith E. Fich:
Optimal Bounds for the Predecessor Problem.
295-304
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems.
312-321
Electronic Edition (ACM DL) BibTeX
- Leonard J. Schulman, Umesh V. Vazirani:
Molecular Scale Heat Engines and Scalable Quantum Computation.
322-329
Electronic Edition (ACM DL) BibTeX
- Lisa Hales, Sean Hallgren:
Quantum Fourier Sampling Simplified.
330-338
Electronic Edition (ACM DL) BibTeX
- Alexander Russell, Michael E. Saks, David Zuckerman:
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model.
339-347
Electronic Edition (ACM DL) BibTeX
- Anna Gál, Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation.
348-357
Electronic Edition (ACM DL) BibTeX
- Ran Raz:
Exponential Separation of Quantum and Classical Communication Complexity.
358-367
Electronic Edition (ACM DL) BibTeX
- Masami Amano, Kazuo Iwama:
Undecidability on Quantum Finite Automata.
368-375
Electronic Edition (ACM DL) BibTeX
- Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.
376-383
Electronic Edition (ACM DL) BibTeX
- Ashwin Nayak, Felix Wu:
The Quantum Query Complexity of Approximating the Median and Related Statistics.
384-393
Electronic Edition (ACM DL) BibTeX
- Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko:
Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme.
394-399
Electronic Edition (ACM DL) BibTeX
- Martin Skutella, Gerhard J. Woeginger:
A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines.
400-407
Electronic Edition (ACM DL) BibTeX
- Klaus Jansen, Lorant Porkolab:
Improved Approximation Schemes for Scheduling Unrelated Parallel Machines.
408-417
Electronic Edition (ACM DL) BibTeX
- Jianer Chen, Antonio Miranda:
A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract).
418-427
Electronic Edition (ACM DL) BibTeX
- Piotr Indyk:
Sublinear Time Algorithms for Metric Space Problems.
428-434
Electronic Edition (ACM DL) BibTeX
- Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces.
435-444
Electronic Edition (ACM DL) BibTeX
- V. S. Anil Kumar, H. Ramesh:
Covering Rectilinear Polygons with Axis-Parallel Rectangles.
445-454
Electronic Edition (ACM DL) BibTeX
- S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel:
Compact Grid Layouts of Multi-Level Networks.
455-463
Electronic Edition (ACM DL) BibTeX
- Tomás Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani:
Complexity of Graph Partition Problems.
464-472
Electronic Edition (ACM DL) BibTeX
- Ming Li, Bin Ma, Lusheng Wang:
Finding Similar Regions in Many Strings.
473-482
Electronic Edition (ACM DL) BibTeX
- Paolo Ferragina, S. Muthukrishnan, Mark de Berg:
Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems.
483-491
Electronic Edition (ACM DL) BibTeX
- Valerie King, Garry Sagert:
A Fully Dynamic Algorithm for Maintaining the Transitive Closure.
492-498
Electronic Edition (ACM DL) BibTeX
- Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe:
Worst-Case and Amortised Optimality in Union-Find (Extended Abstract).
499-506
Electronic Edition (ACM DL) BibTeX
- Victor Y. Pan, Zhao Q. Chen:
The Complexity of the Matrix Eigenproblem.
507-516
Electronic Edition (ACM DL) BibTeX
- Eli Ben-Sasson, Avi Wigderson:
Short Proofs are Narrow - Resolution Made Simple.
517-526
Electronic Edition (ACM DL) BibTeX
- J. Maurice Rojas:
On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract).
527-536
Electronic Edition (ACM DL) BibTeX
- Madhu Sudan, Luca Trevisan, Salil P. Vadhan:
Pseudorandom Generators Without the XOR Lemma (Extended Abstract).
537-546
Electronic Edition (ACM DL) BibTeX
- Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
547-556
Electronic Edition (ACM DL) BibTeX
- Matthew Andrews, Lisa Zhang:
Packet Routing with Arbitrary End-to-End Delay Requirements.
557-565
Electronic Edition (ACM DL) BibTeX
- Gopal Pandurangan, Eli Upfal:
Static and Dynamic Evaluation of QoS Properties.
566-573
Electronic Edition (ACM DL) BibTeX
- Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber:
Efficient Recovery from Power Outage (Extended Abstract).
574-582
Electronic Edition (ACM DL) BibTeX
- Uriel Feige:
Nonmonotonic Phenomena in Packet Routing.
583-591
Electronic Edition (ACM DL) BibTeX
- Marcus Schaefer:
Graph Ramsey Theory and the Polynomial Hierarchy.
592-601
Electronic Edition (ACM DL) BibTeX
- Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling.
602-611
Electronic Edition (ACM DL) BibTeX
- Edith Cohen, Haim Kaplan, Uri Zwick:
Connection Caching.
612-621
Electronic Edition (ACM DL) BibTeX
- Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
Approximating the Throughput of Multiple Machines Under Real-Time Scheduling.
622-631
Electronic Edition (ACM DL) BibTeX
- Miklós Ajtai:
Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract).
632-641
Electronic Edition (ACM DL) BibTeX
- Leslie G. Valiant:
Robust Logics.
642-651
Electronic Edition (ACM DL) BibTeX
- Eugene M. Luks:
Hypergraph Isomorphism and Structural Equivalence of Boolean Functions.
652-658
Electronic Edition (ACM DL) BibTeX
- Adam Klivans, Dieter van Melkebeek:
Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.
659-667
Electronic Edition (ACM DL) BibTeX
- 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
Electronic Edition (ACM DL) BibTeX
- Uri Zwick:
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.
679-687
Electronic Edition (ACM DL) BibTeX
- Sanjeev Arora, George Karakostas:
Approximation Schemes for Minimum Latency Problems.
688-693
Electronic Edition (ACM DL) BibTeX
- Anupam Gupta:
Embedding Tree Metrics Into Low Dimensional Euclidean Spaces.
694-700
Electronic Edition (ACM DL) BibTeX
- Rocco A. Servedio:
Computational Sample Complexity and Attribute-Efficient Learning.
701-710
Electronic Edition (ACM DL) BibTeX
- Johannes Blömer, Jean-Pierre Seifert:
On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice.
711-720
Electronic Edition (ACM DL) BibTeX
- Wojciech Plandowski:
Satisfiability of Word Equations with Constants is in NEXPTIME.
721-725
Electronic Edition (ACM DL) BibTeX
- Jin-yi Cai, Ajay Nerurkar, D. Sivakumar:
Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.
726-735
Electronic Edition (ACM DL) BibTeX
- Piotr Indyk:
Inerpolation of Symmetric Functions and a New Type of Combinatorial Design.
736-740
Electronic Edition (ACM DL) BibTeX
- Michael R. Capalbo, S. Rao Kosaraju:
Small Universal Graphs.
741-749
Electronic Edition (ACM DL) BibTeX
- Yevgeniy Dodis, Sanjeev Khanna:
Design Networks with Bounded Pairwise Distance.
750-759
Electronic Edition (ACM DL) BibTeX
- Gilles Schaeffer:
Random Sampling of Large Planar Maps and Convex Polyhedra.
760-769
Electronic Edition (ACM DL) BibTeX
- Sanjiv Kapoor:
Efficient Computation of Geodesic Shortest Paths.
770-779
Electronic Edition (ACM DL) BibTeX
- Amir M. Ben-Amram, Holger Petersen:
Backing Up in Singly Linked Lists.
780-786
Electronic Edition (ACM DL) BibTeX
Copyright © Sat May 16 23:43:12 2009
by Michael Ley (ley@uni-trier.de)
