| 1990 | Distributed Reactive Systems Are Hard to Synthesize | Amir Pnueli, Roni Rosner |
| 1990 | On Threshold Circuits for Parity | Ramamohan Paturi, Michael E. Saks |
| 1990 | Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions | Mike Paterson, Nicholas Pippenger, Uri Zwick |
| 1990 | On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract) | Christos H. Papadimitriou |
| 1990 | Specified Precision Polynomial Root Isolation is in NC | C. Andrew Neff |
| 1990 | A Fast Algorithm for Optimally Increasing the Edge-Connectivity | Dalit Naor, Dan Gusfield, Charles U. Martel |
| 1990 | Asynchronous PRAMs Are (Almost) as Good as Synchronous PRAMs | Charles U. Martel, Ramesh Subramonian, Arvin Park |
| 1990 | Tight Bounds on the Complexity of Cascaded Decomposition of Automata | Oded Maler, Amir Pnueli |
| 1990 | On the Complexity of Learning from Counterexamples and Membership Queries | Wolfgang Maass, Gyrgy Turn |
| 1990 | Probabilities of Sentences about Very Sparse Random Graphs | James F. Lynch |
| 1990 | Communication Complexity of Algebraic Computation (Extended Abstract) | Zhi-Quan Luo, John N. Tsitsiklis |
| 1990 | Algebraic Methods for Interactive Proof Systems | Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan |
| 1990 | The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume | Lszl Lovsz, Mikls Simonovits |
| 1990 | Decision Problems for Propositional Linear Logic | Patrick Lincoln, John C. Mitchell, Andre Scedrov, Natarajan Shankar |
| 1990 | Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version) | Ming Li |
| 1990 | A (fairly) Simple Circuit that (usually) Sorts | Frank Thomson Leighton, C. Greg Plaxton |
| 1990 | Efficient Parallel Algorithms for Tree-Decomposition and Related Problems | Jens Lagergren |
| 1990 | Complexity of Unification in Free Groups and Free Semi-groups | Antoni Koscielski, Leszek Pacholski |
| 1990 | A Tree-Partitioning Technique with Applications to Expression Evaluation and Term Matching (Extended Abstract) | S. Rao Kosaraju, Arthur L. Delcher |
| 1990 | Approximation through Multicommodity Flow | Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao |
| 1990 | Efficient Distribution-free Learning of Probabilistic Concepts (Extended Abstract) | Michael J. Kearns, Robert E. Schapire |
| 1990 | Inferring Evolutionary History from DNA Sequences (Extended Abstract) | Sampath Kannan, Tandy J. Warnow |
| 1990 | Finite-Memory Automata (Extended Abstract) | Michael Kaminski, Nissim Francez |
| 1990 | Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract) | Christos Kaklamanis, Anna R. Karlin, Frank Thomson Leighton, Victor Milenkovic, Prabhakar Raghavan, Satish Rao, Clark D. Thomborson, A. Tsantilas |
| 1990 | Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract) | Sorin Istrail |