| 1986 | On Sparseness, Ambiguity and other Decision Problems for Acceptors and Transducers. | Oscar H. Ibarra, Bala Ravikumar |
| 1986 | Monotone Boolean Formulas, Distributive Lattices, and the Complexities of Logics, Algebraic Structures, and Computation Structures (Preliminary Report). | Harry B. Hunt III, Richard Edwin Stearns |
| 1986 | Speeding up Random Access Machines by Few Processors. | Friedhelm Meyer auf der Heide |
| 1986 | Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. | Johan Hstad, Bettina Helfrich, J. C. Lagarias, Claus-Peter Schnorr |
| 1986 | On Sparse Oracles Separating Feasible Complexity Classes. | Juris Hartmanis, Lane A. Hemachandra |
| 1986 | Towards Specification and Proof of Asynchronous Systems. | B. Gamatie |
| 1986 | Some Probabilistic Powerdomains in the Category SFP. | David de Frutos-Escrig |
| 1986 | Temporal Reasoning Under Generalized Fairness Constraints. | E. Allen Emerson, Chin-Laung Lei |
| 1986 | Equations in Free Partially Commutative Monoids. | Christine Duboc |
| 1986 | Separating and Testing. | Philippe Darondeau |
| 1986 | Dcomposition de Fonctions Rationnelles. | Christian Choffrut, Marcel Paul Schtzenberger |
| 1986 | Dcidabiit de l'galit des Languages Algbriques Infinitaires Simples. | Didier Caucal |
| 1986 | A Time-Space Tradeoff for Element Distinctness. | Allan Borodin, Faith E. Fich, Friedhelm Meyer auf der Heide, Eli Upfal, Avi Wigderson |
| 1986 | New Upperbounds for Decentralized Extrema-Finding in a Ring of Processors. | Hans L. Bodlaender, Jan van Leeuwen |
| 1986 | Abstract Implementations and Correctness Proofs. | Gilles Bernot, Michel Bidoit, Christine Choppy |
| 1986 | On Generalized Kolmogorov Complexity. | Jos L. Balczar, Ronald V. Book |
| 1986 | Icons and Local Definitions in Logic Programming. | M. A. Nait Abdallah |
| 1986 | A Parallel Statistical Cooling Algorithm. | Emile H. L. Aarts, F. M. J. de Bont, J. H. A. Habers, Peter J. M. van Laarhoven |
| 1985 | Reduced Memory Space for Multi-Dimensional Search Trees (Extended Abstract). | Dan E. Willard |
| 1985 | Groups, Codes and Unambiguous Automata. | Pascal Weil |
| 1985 | Combined Simplicity and Immunity in Relativized NP. | Leen Torenvliet, Peter van Emde Boas |
| 1985 | The Volume of the Union of Many Sheres and Point Inclusion Problems. | Paul G. Spirakis |
| 1985 | Geometric Containment is not Reducible to Pareto Dominance. | Nicola Santoro, Jeffrey B. Sidney, Stuart J. Sidney, Jorge Urrutia |
| 1985 | Translating Polygons in the Plane. | Jrg-Rdiger Sack, Godfried T. Toussaint |
| 1985 | Deriving Stack Semantics Congruent to Standard Denotational Semantics. | Vronique Royer |