| 1990 | Computing with Unreliable Information (Preliminary Version) | Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal |
| 1990 | The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (Extended Abstract) | Shimon Even, Sergio Rajsbaum |
| 1990 | How to Distribute a Dictionary in a Complete Network | Martin Dietzfelbinger, Friedhelm Meyer auf der Heide |
| 1990 | Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers | Robert Cypher, C. Greg Plaxton |
| 1990 | Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version) | Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir |
| 1990 | On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract) | Richard Cole |
| 1990 | Towards Optimal Simulations of Formulas by Bounded-Width Programs | Richard Cleve |
| 1990 | On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) | Allan Borodin, Prasoon Tiwari |
| 1990 | On the Necessity of Occam Algorithms | Raymond A. Board, Leonard Pitt |
| 1990 | Self-Testing/Correcting with Applications to Numerical Problems | Manuel Blum, Michael Luby, Ronitt Rubinfeld |
| 1990 | Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract) | Avrim Blum |
| 1990 | Online Algorithms for Locating Checkpoints | Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan |
| 1990 | On the Power of Randomization in Online Algorithms (Extended Abstract) | Shai Ben-David, Allan Borodin, Richard M. Karp, Gbor Tardos, Avi Wigderson |
| 1990 | The (True) Complexity of Statistical Zero Knowledge | Mihir Bellare, Silvio Micali, Rafail Ostrovsky |
| 1990 | Perfect Zero-Knowledge in Constant Rounds | Mihir Bellare, Silvio Micali, Rafail Ostrovsky |
| 1990 | The Round Complexity of Secure Protocols (Extended Abstract) | Donald Beaver, Silvio Micali, Phillip Rogaway |
| 1990 | On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract) | Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs |
| 1990 | A Separator Theorem for Graphs with an Excluded Minor and its Applications | Noga Alon, Paul D. Seymour, Robin Thomas |
| 1990 | Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract) | Alok Aggarwal, Mark Hansen, Frank Thomson Leighton |
| 1989 | Circuits and Local Computation | Andrew Chi-Chih Yao |
| 1989 | Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues | Brigitte Valle |
| 1989 | An O(log N) Deterministic Packet Routing Scheme (Preliminary Version) | Eli Upfal |
| 1989 | On Aspects of Universality and Performance for Closed Hashing (Extended Abstract) | Jeanette P. Schmidt, Alan Siegel |
| 1989 | On omega-Automata and Temporal Logic (Preliminary Report) | Shmuel Safra, Moshe Y. Vardi |
| 1989 | Inference of Finite Automata Using Homing Sequences (Extended Abstract) | Ronald L. Rivest, Robert E. Schapire |