| 1985 | A General Approach to d-Dimensional Geometric Queries (Extended Abstract) Andrew Chi-Chih Yao, F. Frances Yao |
| 1985 | A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems Dov Harel |
| 1985 | A Parallel Algorithm for the Maximal Path Problem Richard Anderson |
| 1985 | A Probabilistic Algorithm for the Post Office Problem Kenneth L. Clarkson |
| 1985 | A Simple Parallel Algorithm for the Maximal Independent Set Problem Michael Luby |
| 1985 | A Simple Three-Dimensional Real-Time Reliable Cellular Array Péter Gács, John H. Reif |
| 1985 | Algorithms for Routing and Testing Routability of Planar VLSI Layouts Charles E. Leiserson, F. Miller Maley |
| 1985 | An Algorithm for Finding Hamilton Cycles in a Random Graph Béla Bollobás, Trevor I. Fenner, Alan M. Frieze |
| 1985 | An Internal Semantics for Modal Logic: Preliminary Report Ronald Fagin, Moshe Y. Vardi |
| 1985 | An O(\mathop lg n) Expected Rounds Randomized Byzantine Generals Protocol Gabriel Bracha |
| 1985 | Are Search and Decision Problems Computationally Equivalent? Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | Compression and Ranking Andrew V. Goldberg, Michael Sipser |
| 1985 | Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors Erich L. Kaltofen |
| 1985 | Concurrent Dynamic Logic (Extended Abstract) David Peleg |
| 1985 | Constructing a Perfect Matching is in Random NC Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | Doubly Lexical Orderings of Matrices Anna Lubiw |
| 1985 | Dual Integer Linear Programs and the Relationship between their Optima Ron Aharoni, Paul Erdös, Nathan Linial |
| 1985 | Efficient Parallel Solution of Linear Systems Victor Y. Pan, John H. Reif |
| 1985 | Equational Theories and Database Constraints Stavros S. Cosmadakis, Paris C. Kanellakis |
| 1985 | Expanders Obtained from Affine Transformations (Preliminary Version) Shuji Jimbo, Akira Maruoka |
| 1985 | Expanders, Sorting in Rounds and Superconcentrators of Limited Depth Noga Alon |
| 1985 | Fast Algorithms for N-Dimensional Restrictions of Hard Problems Friedhelm Meyer auf der Heide |
| 1985 | Fault Tolerance of Minimal Path Routings in a Network Paul Feldman |
| 1985 | Finding the Median Requires 2n Comparisons Samuel W. Bent, John W. John |
| 1985 | Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report Moshe Y. Vardi, Larry J. Stockmeyer |
| 1985 | Multicommodity Flows in Planar Undirected Graphs and Shortest Paths Hitoshi Suzuki, Takao Nishizeki, Nobuji Saito |
| 1985 | NP Is as Easy as Detecting Unique Solutions Leslie G. Valiant, Vijay V. Vazirani |
| 1985 | On the Expected Behaviour of Disjoint Set Union Algorithms Béla Bollobás, István Simon |
| 1985 | On the Stability of the Ethernet Jonathan Goodman, Albert G. Greenberg, Neal Madras, Peter March |
| 1985 | One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation Faith E. Fich, Friedhelm Meyer auf der Heide, Prabhakar Ragde, Avi Wigderson |
| 1985 | One-Way Functions and Pseudorandom Generators Leonid A. Levin |
| 1985 | Optimal Precision in the Presence of Uncertainty (Preliminary Version) Joseph Y. Halpern, Nimrod Megiddo, Ashfaq A. Munshi |
| 1985 | Polynomial Time Solutions of Some Problems in Computational Algebra Katalin Friedl, Lajos Rónyai |
| 1985 | Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA Robert Sedgewick |
| 1985 | Provable Isomorphisms and Domain Equations in Models of Typed Languages (Preliminary Version) Kim B. Bruce, Giuseppe Longo |
| 1985 | Provably Good Routing in Graphs: Regular Arrays Prabhakar Raghavan, Clark D. Thompson |
| 1985 | Riemann Hypothesis and Finding Roots over Finite Fields Ming-Deh A. Huang |
| 1985 | Self-Organizing Sequential Search and Hilbert's Inequalities Fan R. K. Chung, D. J. Hajela, Paul D. Seymour |
| 1985 | Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract) Pravin M. Vaidya |
| 1985 | Stable Prehension with Three Fingers Brenda S. Baker, Steven Fortune, Eric Grosse |
| 1985 | The Complexity of Backtrack Searches (Preliminary Version) Larry Carter, Larry J. Stockmeyer, Mark N. Wegman |
| 1985 | The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems Dung T. Huynh |
| 1985 | The Cryptographic Security of Truncated Linearly Related Variables Johan Håstad, Adi Shamir |
| 1985 | The Distributed Firing Squad Problem (Preliminary Version) Brian A. Coan, Danny Dolev, Cynthia Dwork, Larry J. Stockmeyer |
| 1985 | The Effect of Updates in Binary Search Trees Joseph C. Culberson |
| 1985 | The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract) Shafi Goldwasser, Silvio Micali, Charles Rackoff |
| 1985 | The Parallel Complexity of Exponentiating Polynomials over Finite Fields Faith E. Fich, Martin Tompa |
| 1985 | The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract) Samuel R. Buss |
| 1985 | The Two-Processor Scheduling Problem is in R-NC Umesh V. Vazirani, Vijay V. Vazirani |
| 1985 | Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract) Umesh V. Vazirani |
| 1985 | Tradeoffs for VLSI Models with Subpolynomial Delay Alok Aggarwal |
| 1985 | Trading Group Theory for Randomness László Babai |
| 1985 | Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency J. W. de Bakker, John-Jules Ch. Meyer, Ernst-Rüdiger Olderog, Jeffery I. Zucker |
| 1985 | White Pebbles Help Robert E. Wilber |