31. STOC 1999: Atlanta, Georgia, USA

• Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys:
  A Constant-Factor Approximation Algorithm for the k-Median Problem (Extended Abstract). 1-10
  
• Kevin D. Wayne:
  A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. 11-18
  
• 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
  
• Funda Ergün, Ravi Kumar, Ronitt Rubinfeld:
  Fast Approximate PCPs. 41-50
  
• Marcos A. Kiwi, Frédéric Magniez, Miklos Santha:
  Approximate Testing with Relative Error. 51-60
  
• Uri Zwick:
  All Pairs Lightest Shortest Paths. 61-69
  
• Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan:
  Unique Maximum Matching Algorithms. 70-78
  
• 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
  
• Noam Nisan, Amir Ronen:
  Algorithmic Mechanism Design (Extended Abstract). 129-140
  
• 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
  
• Ran Raz, Omer Reingold:
  On Recycling the Randomness of States in Space Bounded Computation. 159-168
  
• Giovanni Di Crescenzo, Russell Impagliazzo:
  Security-Preserving Hardness-Amplification for Any Regular One-Way Function. 169-178
  
• Jeff Edmonds:
  Scheduling in the Dark. 179-188
  
• 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
  
• Oded Goldreich, Dana Ron, Madhu Sudan:
  Chinese Remaindering with Errors. 225-234
  
• Vadim Olshevsky, Mohammad Amin Shokrollahi:
  A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. 235-244
  
• Moni Naor, Benny Pinkas:
  Oblivious Transfer and Polynomial Evaluation. 245-254
  
• 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
  
• Fang Chen, László Lovász, Igor Pak:
  Lifting Markov Chains to Speed up Mixing. 275-281
  
• László Lovász, Ravi Kannan:
  Faster Mixing via Average Conductance. 282-287
  
• Leonard J. Schulman, Vijay V. Vazirani:
  Majorizing Estimators and the Approximation of #P-Complete Problems. 288-294
  
• Paul Beame, Faith E. Fich:
  Optimal Bounds for the Predecessor Problem. 295-304
  
• 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
  
• Lisa Hales, Sean Hallgren:
  Quantum Fourier Sampling Simplified. 330-338
  
• Alexander Russell, Michael E. Saks, David Zuckerman:
  Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. 339-347
  
• Anna Gál, Adi Rosén:
  A Theorem on Sensitivity and Applications in Private Computation. 348-357
  
• Ran Raz:
  Exponential Separation of Quantum and Classical Communication Complexity. 358-367
  
• Masami Amano, Kazuo Iwama:
  Undecidability on Quantum Finite Automata. 368-375
  
• 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
  
• Piotr Indyk:
  Sublinear Time Algorithms for Metric Space Problems. 428-434
  
• Allan Borodin, Rafail Ostrovsky, Yuval Rabani:
  Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. 435-444
  
• V. S. Anil Kumar, H. Ramesh:
  Covering Rectilinear Polygons with Axis-Parallel Rectangles. 445-454
  
• 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
  
• Ming Li, Bin Ma, Lusheng Wang:
  Finding Similar Regions in Many Strings. 473-482
  
• 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
  
• Victor Y. Pan, Zhao Q. Chen:
  The Complexity of the Matrix Eigenproblem. 507-516
  
• Eli Ben-Sasson, Avi Wigderson:
  Short Proofs are Narrow - Resolution Made Simple. 517-526
  
• 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
  
• Matthew Andrews, Lisa Zhang:
  Packet Routing with Arbitrary End-to-End Delay Requirements. 557-565
  
• Gopal Pandurangan, Eli Upfal:
  Static and Dynamic Evaluation of QoS Properties. 566-573
  
• Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber:
  Efficient Recovery from Power Outage (Extended Abstract). 574-582
  
• Uriel Feige:
  Nonmonotonic Phenomena in Packet Routing. 583-591
  
• Marcus Schaefer:
  Graph Ramsey Theory and the Polynomial Hierarchy. 592-601
  
• Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh:
  The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. 602-611
  
• Edith Cohen, Haim Kaplan, Uri Zwick:
  Connection Caching. 612-621
  
• Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber:
  Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. 622-631
  
• Miklós Ajtai:
  Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). 632-641
  
• Leslie G. Valiant:
  Robust Logics. 642-651
  
• Eugene M. Luks:
  Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. 652-658
  
• Adam 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
  
• Sanjeev Arora, George Karakostas:
  Approximation Schemes for Minimum Latency Problems. 688-693
  
• Anupam Gupta:
  Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. 694-700
  
• Rocco A. Servedio:
  Computational Sample Complexity and Attribute-Efficient Learning. 701-710
  
• Johannes Blömer, Jean-Pierre Seifert:
  On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. 711-720
  
• Wojciech Plandowski:
  Satisfiability of Word Equations with Constants is in NEXPTIME. 721-725
  
• Jin-yi Cai, Ajay Nerurkar, D. Sivakumar:
  Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. 726-735
  
• Piotr Indyk:
  Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. 736-740
  
• Michael R. Capalbo, S. Rao Kosaraju:
  Small Universal Graphs. 741-749
  
• Yevgeniy Dodis, Sanjeev Khanna:
  Design Networks with Bounded Pairwise Distance. 750-759
  
• Gilles Schaeffer:
  Random Sampling of Large Planar Maps and Convex Polyhedra. 760-769
  
• Sanjiv Kapoor:
  Efficient Computation of Geodesic Shortest Paths. 770-779
  
• Amir M. Ben-Amram, Holger Petersen:
  Backing Up in Singly Linked Lists. 780-786