| 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 | On targeting Markov segments. | Moses Charikar, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins |
| 1999 | A Constant-Factor Approximation Algorithm for the | Moses Charikar, Sudipto Guha, va Tardos, David B. Shmoys |
| 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 | Small Universal Graphs. | Michael R. Capalbo, S. Rao Kosaraju |
| 1999 | Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). | Ran Canetti, Rafail Ostrovsky |
| 1999 | Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. | Jin-yi Cai, Ajay Nerurkar, D. Sivakumar |
| 1999 | Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. | Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi |
| 1999 | Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. | Allan Borodin, Rafail Ostrovsky, Yuval Rabani |
| 1999 | Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. | Allan Borodin, Rafail Ostrovsky, Yuval Rabani |
| 1999 | On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. | Johannes Blmer, Jean-Pierre Seifert |
| 1999 | Short Proofs are Narrow - Resolution Made Simple. | Eli Ben-Sasson, Avi Wigderson |
| 1999 | Backing Up in Singly Linked Lists. | Amir M. Ben-Amram, Holger Petersen |
| 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 | Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. | Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber |
| 1999 | Minimizing the Flow Time Without Migration. | Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev |
| 1999 | Approximation Schemes for Minimum Latency Problems. | Sanjeev Arora, George Karakostas |
| 1999 | Packet Routing with Arbitrary End-to-End Delay Requirements. | Matthew Andrews, Lisa Zhang |
| 1999 | Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. | Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani |
| 1999 | Undecidability on Quantum Finite Automata. | Masami Amano, Kazuo Iwama |
| 1999 | Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). | Stephen Alstrup, Amir M. Ben-Amram, Theis Rauhe |
| 1999 | Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). | Mikls Ajtai |
| 1998 | Finding Almost-Satisfying Assignments. | Uri Zwick |
| 1998 | Computing Local Dimension of a Semialgebraic Set. | Nicolai N. Vorobjov Jr. |