| 1999 | A Lower Bound for Primality. Eric Allender, Michael E. Saks, Igor E. Shparlinski |
| 1999 | A Note on the Shortest Lattice Vector Problem. Ravi Kumar, D. Sivakumar |
| 1999 | Applications of a New Transference Theorem to Ajtai's Connection Factor. Jin-Yi Cai |
| 1999 | Circuit Lower Bounds Collapse Relativized Complexity Classes. Richard Beigel, Alexis Maciel |
| 1999 | Comparing Entropies in Statistical Zero Knowledge with Applications to the Structure of SZK. Oded Goldreich, Salil P. Vadhan |
| 1999 | Complexity of k-SAT. Russell Impagliazzo, Ramamohan Paturi |
| 1999 | Complicated Complementations. Harry Buhrman, Leen Torenvliet |
| 1999 | Computing from Partial Solutions. Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank |
| 1999 | De-Randomizing BPP: The State of the Art. Avi Wigderson |
| 1999 | Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. Amir Shpilka, Avi Wigderson |
| 1999 | Deterministic Amplification of Space-Bounded Probabilistic Algorithms. Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson |
| 1999 | Gaps in Bounded Query Hierarchies. Richard Beigel |
| 1999 | Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). Marcus Schaefer |
| 1999 | Learning DNF by Approximating Inclusion-Exclusion Formulae. Jun Tarui, Tatsuie Tsukiji |
| 1999 | Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
| 1999 | Non-Automatizability of Bounded-Depth Frege Proofs. Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi |
| 1999 | On Monotone Planar Circuits. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum |
| 1999 | On the Complexity of Diophantine Geometry in Low Dimensions (Abstract). J. Maurice Rojas |
| 1999 | Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999 |
| 1999 | Proofs, Codes, and Polynomial-Time Reducibilities. Ravi Kumar, D. Sivakumar |
| 1999 | Pseudorandom Generators without the XOR Lemma (Abstract). Madhu Sudan, Luca Trevisan, Salil P. Vadhan |
| 1999 | Quantum Bounded Query Complexity. Harry Buhrman, Wim van Dam |
| 1999 | Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. John Watrous |
| 1999 | Query Order and NP-Completeness. Jack Jie Dai, Jack H. Lutz |
| 1999 | Short Proofs Are Narrow - Resolution Made Simple (Abstract). Eli Ben-Sasson, Avi Wigderson |
| 1999 | Some Recent Progress on the Complexity of Lattice Problems. Jin-Yi Cai |
| 1999 | Stronger Separations for Random-Self-Reducibility, Rounds, and Advice. László Babai, Sophie Laplante |
| 1999 | The Communication Complexity of Pointer Chasing Applications of Entropy and Sampling (Abstract). Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh |
| 1999 | The Complexity of Solving Equations over Finite Groups. Mikael Goldmann, Alexander Russell |
| 1999 | The Expected Size of Heilbronn's Triangles. Tao Jiang, Ming Li, Paul M. B. Vitányi |
| 1999 | Upper Semilattice of Binary Strings with the Relation "x is Simple Conditional to y". Andrei A. Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |