| 1990 | On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets | Mitsunori Ogiwara, Osamu Watanabe |
| 1990 | Psuedorandom Generators for Space-Bounded Computation | Noam Nisan |
| 1990 | Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks | Moni Naor, Moti Yung |
| 1990 | Small-bias Probability Spaces: Efficient Constructions and Applications | Joseph Naor, Moni Naor |
| 1990 | Output Sensitive Construction of Levels and Voronoi Diagrams in R^d of Order 1 to k | Ketan Mulmuley |
| 1990 | Separators in Two and Three Dimensions | Gary L. Miller, William P. Thurston |
| 1990 | The Computational Complexity of Universal Hashing | Yishay Mansour, Noam Nisan, Prasoon Tiwari |
| 1990 | Approximate Inclusion-Exclusion | Nathan Linial, Noam Nisan |
| 1990 | The Number Field Sieve | Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse, John M. Pollard |
| 1990 | On the Complexity of Computing a Grbner Basis for the Radical of a Zero Dimensional Ideal | Yagati N. Lakshman |
| 1990 | Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities | Philip N. Klein, Clifford Stein, va Tardos |
| 1990 | Quantitative Steinitz's Theorems with Applications to Multifingered Grasping | David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap |
| 1990 | The Undecidability of the Semi-Unification Problem (Preliminary Report) | A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn |
| 1990 | Efficient Robust Parallel Computations (Extended Abstract) | Zvi M. Kedem, Krishna V. Palem, Paul G. Spirakis |
| 1990 | An Optimal Algorithm for On-line Bipartite Matching | Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani |
| 1990 | Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs | Ming-Yang Kao, Philip N. Klein |
| 1990 | Computing in Quotient Groups | William M. Kantor, Eugene M. Luks |
| 1990 | Pseudo-Random Generators under Uniform Assumptions | Johan Hstad |
| 1990 | Decidability of the Multiplicity Equivalence of Multitape Finite Automata | Tero Harju, Juhani Karhumki |
| 1990 | Optimal Randomized Algorithms for Local Sorting and Set-Maxima | Wayne Goddard, Valerie King, Leonard J. Schulman |
| 1990 | Not All Keys Can Be Hashed in Constant Time (Preliminary Version) | Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1990 | BLASTING through the Information Theoretic Barrier with FUSION TREES | Michael L. Fredman, Dan E. Willard |
| 1990 | The Information Theory Bound Is Tight for Selection in a Heap | Greg N. Frederickson |
| 1990 | The Wakeup Problem (Extended Abstract) | Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld |
| 1990 | Witness Indistinguishable and Witness Hiding Protocols | Uriel Feige, Adi Shamir |