| 1990 | A Separator Theorem for Graphs with an Excluded Minor and its Applications Noga Alon, Paul D. Seymour, Robin Thomas |
| 1990 | A Technique for Lower Bounding the Cover Time David Zuckerman |
| 1990 | An Optimal Algorithm for On-line Bipartite Matching Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani |
| 1990 | Approximate Inclusion-Exclusion Nathan Linial, Noam Nisan |
| 1990 | BLASTING through the Information Theoretic Barrier with FUSION TREES Michael L. Fredman, Dan E. Willard |
| 1990 | Coherent Functions and Program Checkers (Extended Abstract) Andrew Chi-Chih Yao |
| 1990 | Computing in Quotient Groups William M. Kantor, Eugene M. Luks |
| 1990 | Computing with Unreliable Information (Preliminary Version) Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal |
| 1990 | Decidability of the Multiplicity Equivalence of Multitape Finite Automata Tero Harju, Juhani Karhumäki |
| 1990 | Deterministic Sampling-A New Technique for Fast Pattern Matching Uzi Vishkin |
| 1990 | Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers Robert Cypher, C. Greg Plaxton |
| 1990 | Efficient Computation on Oblivious RAMs Rafail Ostrovsky |
| 1990 | Efficient Robust Parallel Computations (Extended Abstract) Zvi M. Kedem, Krishna V. Palem, Paul G. Spirakis |
| 1990 | Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates Mario Szegedy |
| 1990 | How to Distribute a Dictionary in a Complete Network Martin Dietzfelbinger, Friedhelm Meyer auf der Heide |
| 1990 | Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract) Avrim Blum |
| 1990 | Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities Philip N. Klein, Clifford Stein, Éva Tardos |
| 1990 | Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines Johannes A. La Poutré |
| 1990 | Monotone Circuits for Matching Require Linear Depth Ran Raz, Avi Wigderson |
| 1990 | Not All Keys Can Be Hashed in Constant Time (Preliminary Version) Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1990 | On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets Mitsunori Ogiwara, Osamu Watanabe |
| 1990 | On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal Yagati N. Lakshman |
| 1990 | On the Complexity of Local Search (Extended Abstract) Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis |
| 1990 | On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version) Allan Borodin, Prasoon Tiwari |
| 1990 | On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract) Richard Cole |
| 1990 | On the Necessity of Occam Algorithms Raymond A. Board, Leonard Pitt |
| 1990 | On the Power of Randomization in Online Algorithms (Extended Abstract) Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson |
| 1990 | On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract) Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs |
| 1990 | One-Way Functions are Necessary and Sufficient for Secure Signatures John Rompel |
| 1990 | Online Algorithms for Locating Checkpoints Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan |
| 1990 | Optimal Disk I/O with Parallel Block Transfer (Extended Abstract) Jeffrey Scott Vitter, Elizabeth A. M. Shriver |
| 1990 | Optimal Randomized Algorithms for Local Sorting and Set-Maxima Wayne Goddard, Valerie King, Leonard J. Schulman |
| 1990 | Output Sensitive Construction of Levels and Voronoi Diagrams in R^d of Order 1 to k Ketan Mulmuley |
| 1990 | Perfect Zero-Knowledge in Constant Rounds Mihir Bellare, Silvio Micali, Rafail Ostrovsky |
| 1990 | Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA Harriet Ortiz |
| 1990 | Pseudo-Random Generators under Uniform Assumptions Johan Håstad |
| 1990 | Psuedorandom Generators for Space-Bounded Computation Noam Nisan |
| 1990 | Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks Moni Naor, Moti Yung |
| 1990 | Quantifiers and Approximation (Extended Abstract) Alessandro Panconesi, Desh Ranjan |
| 1990 | Quantitative Steinitz's Theorems with Applications to Multifingered Grasping David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap |
| 1990 | Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version) Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir |
| 1990 | Searching for Primitive Roots in Finite Fields Victor Shoup |
| 1990 | Self-Testing/Correcting with Applications to Numerical Problems Manuel Blum, Michael Luby, Ronitt Rubinfeld |
| 1990 | Separators in Two and Three Dimensions Gary L. Miller, William P. Thurston |
| 1990 | Small-bias Probability Spaces: Efficient Constructions and Applications Joseph Naor, Moni Naor |
| 1990 | Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract) Alok Aggarwal, Mark Hansen, Frank Thomson Leighton |
| 1990 | The (True) Complexity of Statistical Zero Knowledge Mihir Bellare, Silvio Micali, Rafail Ostrovsky |
| 1990 | The Analysis of Closed Hashing under Limited Randomness (Extended Abstract) Jeanette P. Schmidt, Alan Siegel |
| 1990 | The Computational Complexity of Universal Hashing Yishay Mansour, Noam Nisan, Prasoon Tiwari |
| 1990 | The Discrete Log is Very Discreet A. W. Schrift, Adi Shamir |
| 1990 | The Information Theory Bound Is Tight for Selection in a Heap Greg N. Frederickson |
| 1990 | The Number Field Sieve Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse, John M. Pollard |
| 1990 | The Round Complexity of Secure Protocols (Extended Abstract) Donald Beaver, Silvio Micali, Phillip Rogaway |
| 1990 | The Undecidability of the Semi-Unification Problem (Preliminary Report) A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn |
| 1990 | The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (Extended Abstract) Shimon Even, Sergio Rajsbaum |
| 1990 | The Wakeup Problem (Extended Abstract) Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld |
| 1990 | Towards Optimal Simulations of Formulas by Bounded-Width Programs Richard Cleve |
| 1990 | Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs Ming-Yang Kao, Philip N. Klein |
| 1990 | Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences Rajamani Sundar, Robert Endre Tarjan |
| 1990 | Witness Indistinguishable and Witness Hiding Protocols Uriel Feige, Adi Shamir |