| 1999 | A Constant-Factor Approximation Algorithm for the Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys |
| 1999 | A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. Vadim Olshevsky, Mohammad Amin Shokrollahi |
| 1999 | A Fully Dynamic Algorithm for Maintaining the Transitive Closure. Valerie King, Garry Sagert |
| 1999 | A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. Amit Chakrabarti, Bernard Chazelle, Benjamin Gum, Alexey Lvov |
| 1999 | A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. Martin Skutella, Gerhard J. Woeginger |
| 1999 | A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. Kevin D. Wayne |
| 1999 | A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). Jianer Chen, Antonio Miranda |
| 1999 | A Theorem on Sensitivity and Applications in Private Computation. Anna Gál, Adi Rosén |
| 1999 | Algorithmic Mechanism Design (Extended Abstract). Noam Nisan, Amir Ronen |
| 1999 | All Pairs Lightest Shortest Paths. Uri Zwick |
| 1999 | Approximate Testing with Relative Error. Marcos A. Kiwi, Frédéric Magniez, Miklos Santha |
| 1999 | Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber |
| 1999 | Approximation Schemes for Minimum Latency Problems. Sanjeev Arora, George Karakostas |
| 1999 | Backing Up in Singly Linked Lists. Amir M. Ben-Amram, Holger Petersen |
| 1999 | Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum |
| 1999 | Chinese Remaindering with Errors. Oded Goldreich, Dana Ron, Madhu Sudan |
| 1999 | Compact Grid Layouts of Multi-Level Networks. S. Muthukrishnan, Mike Paterson, Süleyman Cenk Sahinalp, Torsten Suel |
| 1999 | Complexity of Graph Partition Problems. Tomás Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani |
| 1999 | Computational Sample Complexity and Attribute-Efficient Learning. Rocco A. Servedio |
| 1999 | Connection Caching. Edith Cohen, Haim Kaplan, Uri Zwick |
| 1999 | Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). Luca Trevisan |
| 1999 | Covering Rectilinear Polygons with Axis-Parallel Rectangles. V. S. Anil Kumar, H. Ramesh |
| 1999 | Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani |
| 1999 | Design Networks with Bounded Pairwise Distance. Yevgeniy Dodis, Sanjeev Khanna |
| 1999 | Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). Miklós Ajtai |
| 1999 | Efficient Computation of Geodesic Shortest Paths. Sanjiv Kapoor |
| 1999 | Efficient Recovery from Power Outage (Extended Abstract). Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber |
| 1999 | Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. Anupam Gupta |
| 1999 | Exploiting Regularities in Web Traffic Patterns for Cache Replacement. Edith Cohen, Haim Kaplan |
| 1999 | Exponential Separation of Quantum and Classical Communication Complexity. Ran Raz |
| 1999 | Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. Ran Raz, Omer Reingold, Salil P. Vadhan |
| 1999 | Fast Approximate PCPs. Funda Ergün, Ravi Kumar, Ronitt Rubinfeld |
| 1999 | Faster Mixing via Average Conductance. László Lovász, Ravi Kannan |
| 1999 | Finding Similar Regions in Many Strings. Ming Li, Bin Ma, Lusheng Wang |
| 1999 | From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. Christian Scheideler, Berthold Vöcking |
| 1999 | Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. Adam R. Klivans, Dieter van Melkebeek |
| 1999 | Graph Ramsey Theory and the Polynomial Hierarchy. Marcus Schaefer |
| 1999 | Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. Jin-Yi Cai, Ajay Nerurkar, D. Sivakumar |
| 1999 | Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. Eugene M. Luks |
| 1999 | Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. Klaus Jansen, Lorant Porkolab |
| 1999 | Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). Yuval Ishai, Eyal Kushilevitz |
| 1999 | Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. Piotr Indyk |
| 1999 | Lifting Markov Chains to Speed up Mixing. Fang Chen, László Lovász, Igor Pak |
| 1999 | Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
| 1999 | Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. Allan Borodin, Rafail Ostrovsky, Yuval Rabani |
| 1999 | Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. Alexander Russell, Michael E. Saks, David Zuckerman |
| 1999 | Majorizing Estimators and the Approximation of #P-Complete Problems. Leonard J. Schulman, Vijay V. Vazirani |
| 1999 | Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko |
| 1999 | Minimizing the Flow Time Without Migration. Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev |
| 1999 | Molecular Scale Heat Engines and Scalable Quantum Computation. Leonard J. Schulman, Umesh V. Vazirani |
| 1999 | Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. Paolo Ferragina, S. Muthukrishnan, Mark de Berg |
| 1999 | Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis |
| 1999 | Nonmonotonic Phenomena in Packet Routing. Uriel Feige |
| 1999 | Oblivious Transfer and Polynomial Evaluation. Moni Naor, Benny Pinkas |
| 1999 | On Recycling the Randomness of States in Space Bounded Computation. Ran Raz, Omer Reingold |
| 1999 | On targeting Markov segments. Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins |
| 1999 | On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. Johannes Blömer, Jean-Pierre Seifert |
| 1999 | On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). J. Maurice Rojas |
| 1999 | One-Way Functions Are Essential for Single-Server Private Information Retrieval. Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Tal Malkin |
| 1999 | Optimal Bounds for the Predecessor Problem. Paul Beame, Faith E. Fich |
| 1999 | Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, Hsing-Kuo Wong |
| 1999 | Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. Uri Zwick |
| 1999 | PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra |
| 1999 | Packet Routing with Arbitrary End-to-End Delay Requirements. Matthew Andrews, Lisa Zhang |
| 1999 | Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA Jeffrey Scott Vitter, Lawrence L. Larmore, Frank Thomson Leighton |
| 1999 | Pseudorandom Generators Without the XOR Lemma (Extended Abstract). Madhu Sudan, Luca Trevisan, Salil P. Vadhan |
| 1999 | Quantum Fourier Sampling Simplified. Lisa Hales, Sean Hallgren |
| 1999 | Random Sampling of Large Planar Maps and Convex Polyhedra. Gilles Schaeffer |
| 1999 | Robust Logics. Leslie G. Valiant |
| 1999 | Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
| 1999 | Satisfiability of Word Equations with Constants is in NEXPTIME. Wojciech Plandowski |
| 1999 | Scheduling Data Transfers in a Network and the Set Scheduling Problem. Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, Éva Tardos |
| 1999 | Scheduling in the Dark. Jeff Edmonds |
| 1999 | Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). Ran Canetti, Rafail Ostrovsky |
| 1999 | Security-Preserving Hardness-Amplification for Any Regular One-Way Function. Giovanni Di Crescenzo, Russell Impagliazzo |
| 1999 | Short Proofs are Narrow - Resolution Made Simple. Eli Ben-Sasson, Avi Wigderson |
| 1999 | Small Universal Graphs. Michael R. Capalbo, S. Rao Kosaraju |
| 1999 | Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. David Gamarnik |
| 1999 | Static and Dynamic Evaluation of QoS Properties. Gopal Pandurangan, Eli Upfal |
| 1999 | Sublinear Time Algorithms for Metric Space Problems. Piotr Indyk |
| 1999 | Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. Allan Borodin, Rafail Ostrovsky, Yuval Rabani |
| 1999 | The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh |
| 1999 | The Complexity of the Matrix Eigenproblem. Victor Y. Pan, Zhao Q. Chen |
| 1999 | The Quantum Query Complexity of Approximating the Median and Related Statistics. Ashwin Nayak, Felix Wu |
| 1999 | Undecidability on Quantum Finite Automata. Masami Amano, Kazuo Iwama |
| 1999 | Unique Maximum Matching Algorithms. Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan |
| 1999 | Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe |