| 1990 | Counting and Cutting Cycles of Lines and Rods in Space | Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Richard Pollack, Raimund Seidel, Micha Sharir, Jack Snoeyink |
| 1990 | Triangulating a Simple Polygon in Linear Time | Bernard Chazelle |
| 1990 | Approximate String Matching in Sublinear Expected Time | William I. Chang, Eugene L. Lawler |
| 1990 | Bounds on Tradeoffs between Randomness and Communication Complexity | Ran Canetti, Oded Goldreich |
| 1990 | On the Predictability of Coupled Automata: An Allegory about Chaos | Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis |
| 1990 | Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract) | Jehoshua Bruck, Roman Smolensky |
| 1990 | Some Tools for Approximate 3-Coloring (Extended Abstract) | Avrim Blum |
| 1990 | Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain | Avrim Blum |
| 1990 | Provably Good Mesh Generation | Marshall W. Bern, David Eppstein, John R. Gilbert |
| 1990 | Some Triply-Logarithmic Parallel Algorithms (Extended Abstract) | Omer Berkman, Joseph F. JJ, Sridhar Krishnamurthy, Ramakrishna Thurimella, Uzi Vishkin |
| 1990 | Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract) | Mark de Berg, Mark H. Overmars |
| 1990 | Randomness in Interactive Proofs | Mihir Bellare, Oded Goldreich, Shafi Goldwasser |
| 1990 | Communication-Space Tradeoffs for Unrestricted Protocols | Paul Beame, Martin Tompa, Peiyuan Yan |
| 1990 | Time-Space Tradeoffs for Undirected Graph Traversal | Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa |
| 1990 | Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract) | Paul Bay, Gianfranco Bilardi |
| 1990 | On the Diameter of Finite Groups | Lszl Babai, Gbor Hetyei, William M. Kantor, Alexander Lubotzky, kos Seress |
| 1990 | Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols | Lszl Babai, Lance Fortnow, Carsten Lund |
| 1990 | A Characterization of \sharp P Arithmetic Straight Line Programs | Lszl Babai, Lance Fortnow |
| 1990 | A Dining Philosophers Algorithm with Polynomial Response Time | Baruch Awerbuch, Michael E. Saks |
| 1990 | Network Synchronization with Polylogarithmic Overhead | Baruch Awerbuch, David Peleg |
| 1990 | Sparse Partitions (Extended Abstract) | Baruch Awerbuch, David Peleg |
| 1990 | Communication-Optimal Maintenance of Replicated Information | Baruch Awerbuch, Israel Cidon, Shay Kutten |
| 1990 | Are Wait-Free Algorithms Fast? (Extended Abstract) | Hagit Attiya, Nancy A. Lynch, Nir Shavit |
| 1990 | Fault Tolerant Sorting Network | Shay Assaf, Eli Upfal |
| 1990 | Learning Conjunctions of Horn Clauses (Extended Abstract) | Dana Angluin, Michael Frazier, Leonard Pitt |