| 1990 | Coloring Inductive Graphs On-Line | Sandy Irani |
| 1990 | No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random | Russell Impagliazzo, Leonid A. Levin |
| 1990 | Simplifying Nested Radicals and Solving Polynomials by Radicals in Minimum Depth | Gwoboa Horng, Ming-Deh A. Huang |
| 1990 | On the Power of Small-Depth Threshold Circuits | Johan Hstad, Mikael Goldmann |
| 1990 | Deciding Properties of Nonregular Programs (Preliminary Version) | David Harel, Danny Raz |
| 1990 | Matrix Decomposition Problem Is Complete for the Average Case | Yuri Gurevich |
| 1990 | Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents | Dima Grigoriev, Marek Karpinski, Michael F. Singer |
| 1990 | Security Preserving Amplification of Hardness | Oded Goldreich, Russell Impagliazzo, Leonid A. Levin, Ramarathnam Venkatesan, David Zuckerman |
| 1990 | Exact Identification of Circuits Using Fixed Points of Amplification Functions (Extended Abstract) | Sally A. Goldman, Michael J. Kearns, Robert E. Schapire |
| 1990 | Robust Separations in Inductive Inference | Mark A. Fulk |
| 1990 | Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths | Michael L. Fredman, Dan E. Willard |
| 1990 | Augmenting Graphs to Meet Edge-Connectivity Requirements | Andrs Frank |
| 1990 | Drawing Graphs in the Plane with High Resolution | Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis, Emo Welzl, Gerhard J. Woeginger |
| 1990 | Permuting | Faith E. Fich, J. Ian Munro, Patricio V. Poblete |
| 1990 | Competitive k-Server Algorithms (Extended Abstract) | Amos Fiat, Yuval Rabani, Yiftach Ravid |
| 1990 | Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract) | Uriel Feige, Dror Lapidot, Adi Shamir |
| 1990 | Computing with Snakes in Directed Networks of Automata (Extended Abstract) | Shimon Even, Ami Litman, Peter Winkler |
| 1990 | An Approach for Proving Lower Bounds: Solution of Gilbert-Pollak's Conjecture on Steiner Ratio | Ding-Zhu Du, Frank K. Hwang |
| 1990 | Faster Tree Pattern Matching | Moshe Dubiner, Zvi Galil, Edith Magen |
| 1990 | Perfectly Secure Message Transmission | Danny Dolev, Cynthia Dwork, Orli Waarts, Moti Yung |
| 1990 | Exploring an Unknown Graph (Extended Abstract) | Xiaotie Deng, Christos H. Papadimitriou |
| 1990 | On the Exact Complexity of String Matching (Extended Abstract) | Livio Colussi, Zvi Galil, Raffaele Giancarlo |
| 1990 | Online Algorithms for Finger Searching (Extended Abstract) | Richard Cole, Arvind Raghunathan |
| 1990 | Private Computations Over the Integers (Extended Abstract) | Benny Chor, Mihly Gerb-Graus, Eyal Kushilevitz |
| 1990 | New Results on Dynamic Planar Point Location | Siu-Wing Cheng, Ravi Janardan |