| 1990 | Local Optimization and the Traveling Salesman Problem. | David S. Johnson |
| 1990 | Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract). | Mark Jerrum, Alistair Sinclair |
| 1990 | Language Learning by a "Team" (Extended Abstract). | Sanjay Jain, Arun Sharma |
| 1990 | A Domain-Theoretic Model for a Higher-Order Process Calculus. | Radha Jagadeesan, Prakash Panangaden |
| 1990 | On the Rectilinear Art Gallery Problem (Extended Abstract). | Frank Hoffmann |
| 1990 | A Theory of Communicating Processes with Value-Passing. | Matthew Hennessy, Anna Inglfsdttir |
| 1990 | Randomized Incremental Construction of Delaunay and Voronoi Diagrams. | Leonidas J. Guibas, Donald E. Knuth, Micha Sharir |
| 1990 | An Efficient Algorithm for Branching Bisimulation and Stuttering Equivalence. | Jan Friso Groote, Frits W. Vaandrager |
| 1990 | An Input-Size/Output-Size Trade-Off in the Time-Complexity of Rectilinear Hidden Surface Removal (Preliminary Version). | Michael T. Goodrich, Mikhail J. Atallah, Mark H. Overmars |
| 1990 | On the Composition of Zero-Knowledge Proof Systems. | Oded Goldreich, Hugo Krawczyk |
| 1990 | Nondeterministic Computations in Sublogarithmic Space and Space Constructibility. | Viliam Geffert |
| 1990 | Analytic Variations on the Common Subexpression Problem. | Philippe Flajolet, Paolo Sipala, Jean-Marc Steyaert |
| 1990 | Concurrency, Automata and Domains. | Manfred Droste |
| 1990 | Determining the Separation of Preprocessed Polyhedra - A Unified Approach. | David P. Dobkin, David G. Kirkpatrick |
| 1990 | A New Universal Class of Hash Functions and Dynamic Hashing in Real Time. | Martin Dietzfelbinger, Friedhelm Meyer auf der Heide |
| 1990 | Markov Decision Processes and Regular Events (Extended Abstract). | Costas Courcoubetis, Mihalis Yannakakis |
| 1990 | Equational Formulas in Order-Sorted Algebras. | Hubert Comon |
| 1990 | Merging Free Trees in Parallel for Efficient Voronoi Diagram Construction (Preliminary Version). | Richard Cole, Michael T. Goodrich, Colm 'Dnlaing |
| 1990 | Decomposition of Partial Commutations. | Mireille Clerbout, Michel Latteux, Yves Roos |
| 1990 | Iterated Substitutions and Locally Catanative Systems: A Decidability Result in the Binary Case. | Christian Choffrut |
| 1990 | Can A Maximum Flow be Computed on o(nm) Time? | Joseph Cheriyan, Torben Hagerup, Kurt Mehlhorn |
| 1990 | Additional Queries to Random and Pseudorandom Oracles. | Ronald V. Book, Jack H. Lutz, Shouwen Tang |
| 1990 | A Proof System for the Parallel Object-Oriented Language POOL. | Frank S. de Boer |
| 1990 | A New Approach to Maximum Matching in General Graphs. | Norbert Blum |
| 1990 | On-Line Graph Algorithms with SPQR-Trees. | Giuseppe Di Battista, Roberto Tamassia |