| 1985 | 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985 |
| 1985 | A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract) Zvi Galil, Stuart Haber, Moti Yung |
| 1985 | A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract) Josh D. Cohen, Michael J. Fischer |
| 1985 | A Scaling Algorithm for Weighted Matching on General Graphs Harold N. Gabow |
| 1985 | Algebraic Cell Decomposition in NC (Preliminary Version) Dexter Kozen, Chee-Keng Yap |
| 1985 | Amplification of Probabilistic Boolean Formulas Ravi B. Boppana |
| 1985 | An All Pairs Shortest Path Algorithm with Expected Running Time O(n^2 log n) Alistair Moffat, Tadao Takaoka |
| 1985 | An Almost Linear Time and O(n log n + e) Messages Distributed Algorithm for Minimum-Weight Spanning Trees Francis Y. L. Chin, H. F. Ting |
| 1985 | An Application of Simultaneous Approximation in Combinatorial Optimization András Frank, Éva Tardos |
| 1985 | An Optimal Parallel Algorithm for Integer Sorting John H. Reif |
| 1985 | Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version) Paul M. B. Vitányi |
| 1985 | Automatic Verification of Probabilistic Concurrent Finite-State Programs Moshe Y. Vardi |
| 1985 | Average Case Lower Bounds on the Construction and Searching of Partial Orders Harry G. Mairson |
| 1985 | Byzantine Agreement in Constant Expected Time (and Trusting No One) Paul Feldman, Silvio Micali |
| 1985 | Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values Michael Ben-Or, Nathan Linial |
| 1985 | Computing ears and branchings in parallel László Lovász |
| 1985 | Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization Erich L. Kaltofen |
| 1985 | Design and Analysis of Dynamic Huffman Coding (Extended Abstract) Jeffrey Scott Vitter |
| 1985 | Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version) Miklós Ajtai, Avi Wigderson |
| 1985 | Distributed BFS Algorithms Baruch Awerbuch, Robert G. Gallager |
| 1985 | Dynamic Monotone Priorities on Planar Sets (Extended Abstract) Michael J. Fischer, Mike Paterson |
| 1985 | Efficient String Matching in the Presence of Errors Gad M. Landau, Uzi Vishkin |
| 1985 | Equivalences and Transformations of Recursive Definitions Bruno Courcelle |
| 1985 | Factoring with Cyclotomic Polynomials Eric Bach, Jeffrey O. Shallit |
| 1985 | Fast Parallel Computation with Permutation Groups Eugene M. Luks, Pierre McKenzie |
| 1985 | Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials Victor Y. Pan |
| 1985 | Fixed-Point Extensions of First-Order Logic Yuri Gurevich, Saharon Shelah |
| 1985 | Geometrical Realization of Set Systems and Probabilistic Communication Complexity Noga Alon, Peter Frankl, Vojtech Rödl |
| 1985 | How Easy Is Local Search? (Extended Abstract) David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis |
| 1985 | Identification Is Easier Than Decoding Joseph F. JáJá |
| 1985 | Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC Zvi Galil, Victor Y. Pan |
| 1985 | Inferring the Structure of a Markov Chain from its Output Steven Rudich |
| 1985 | Motion Planning in the Presence of Moving Obstacles John H. Reif, Micha Sharir |
| 1985 | Multi-Layer Grid Embeddings Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson |
| 1985 | Nondeterministic versus Probabilistic Linear Search Algorithms Friedhelm Meyer auf der Heide |
| 1985 | On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract) Richard Cole, Alan Siegel |
| 1985 | On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences Micha Sharir, Ron Livne |
| 1985 | On Networks of Noisy Gates Nicholas Pippenger |
| 1985 | Parallel Computational Geometry (Extended Abstract) Alok Aggarwal, Bernard Chazelle, Leonidas J. Guibas, Colm Ó'Dúnlaing, Chee-Keng Yap |
| 1985 | Parallel Tree Contraction and Its Application Gary L. Miller, John H. Reif |
| 1985 | Partial Polymorphic Type Inference Is Undecidable Hans-Juergen Boehm |
| 1985 | Random Polynomial Time Is Equal to Slightly-random Polynomial Time Umesh V. Vazirani, Vijay V. Vazirani |
| 1985 | Randomized Routing on Fat-Trees (Preliminary Version) Ronald I. Greenberg, Charles E. Leiserson |
| 1985 | Recognizing Circle Graphs in Polynomial Time Csaba P. Gabor, Wen-Lian Hsu, Kenneth J. Supowit |
| 1985 | Robin Hood Hashing (Preliminary Report) Pedro Celis, Per-Åke Larson, J. Ian Munro |
| 1985 | Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) Andrew Chi-Chih Yao |
| 1985 | Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time Ming Li |
| 1985 | Slimming Down Search Structures: A Functional Approach to Algorithm Design Bernard Chazelle |
| 1985 | Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks Ming-Deh A. Huang |
| 1985 | Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version) Mikhail J. Atallah, Susanne E. Hambrusch |
| 1985 | The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky |
| 1985 | The Complexity of Facets Resolved Christos H. Papadimitriou, David Wolfe |
| 1985 | The Complexity of Parallel Computation on Matroids Richard M. Karp, Eli Upfal, Avi Wigderson |
| 1985 | The Complexity of Parallel Sorting Friedhelm Meyer auf der Heide, Avi Wigderson |
| 1985 | The Complexity of Recognizing Polyhedral Scenes (Extended Abstract) Lefteris M. Kirousis, Christos H. Papadimitriou |
| 1985 | The Least Weight Subsequence Problem (Extended Abstract) Daniel S. Hirschberg, Lawrence L. Larmore |
| 1985 | Three Theorems on Polynomial Degrees of NP-Sets Klaus Ambos-Spies |
| 1985 | Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract) Benny Chor, Oded Goldreich |
| 1985 | Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results Dorit S. Hochbaum, David B. Shmoys |
| 1985 | Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract) Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch |
| 1985 | Visibility-Polygon Search and Euclidean Shortest Paths Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai |
| 1985 | Why Certain Subgraph Computations Require Only Linear Time Marshall W. Bern, Eugene L. Lawler, A. L. Wong |