| 1989 | 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 |
| 1989 | A New Algorithm for Minimizing Convex Functions over Convex Sets (Extended Abstract) Pravin M. Vaidya |
| 1989 | A Note on the Power of Threshold Circuits Eric Allender |
| 1989 | A Randomized Maximum-Flow Algorithm Joseph Cheriyan, Torben Hagerup |
| 1989 | A Really Temporal Logic Rajeev Alur, Thomas A. Henzinger |
| 1989 | A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract) Ming Li, Paul M. B. Vitányi |
| 1989 | An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract) Michael R. Fellows, Michael A. Langston |
| 1989 | An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) Elias Dahlhaus, Marek Karpinski |
| 1989 | An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract) Bernard Chazelle |
| 1989 | An Optimal Lower Bound on the Number of Variables for Graph Identification Jin-Yi Cai, Martin Fürer, Neil Immerman |
| 1989 | An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract) Vijaya Ramachandran, John H. Reif |
| 1989 | An Upper Bound on the Number of Planar k-Sets János Pach, William L. Steiger, Endre Szemerédi |
| 1989 | Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract) Mark D. Hansen |
| 1989 | Approximation Schemes for Constrained Scheduling Problems Leslie A. Hall, David B. Shmoys |
| 1989 | Area-Optimal Three-Layer Channel Routing Ruth Kuchem, Dorothea Wagner, Frank Wagner |
| 1989 | Asymptotically Fast Algorithms for Spherical and Related Transforms James R. Driscoll, Dennis M. Healy Jr. |
| 1989 | Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract) Stephen A. Cook, Bruce M. Kapron |
| 1989 | Computational Complexity of Roots of Real Functions (Extended Abstract) Ker-I Ko |
| 1989 | Computing Irreducible Representations of Finite Groups László Babai, Lajos Rónyai |
| 1989 | Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders Milena Mihail |
| 1989 | Constant Depth Circuits, Fourier Transform, and Learnability Nathan Linial, Yishay Mansour, Noam Nisan |
| 1989 | Datalog vs. First-Order Logic Miklós Ajtai, Yuri Gurevich |
| 1989 | Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract) Martín Abadi, Joseph Y. Halpern |
| 1989 | Decision Versus Search Problems in Super-Polynomial Time Russell Impagliazzo, Gábor Tardos |
| 1989 | Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract) Aviad Cohen, Avi Wigderson |
| 1989 | Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic Victor Milenkovic |
| 1989 | Dynamically Computing the Maxima of Decomposable Functions, with Applications David P. Dobkin, Subhash Suri |
| 1989 | Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids Harold N. Gabow, Ying Xu |
| 1989 | Efficient Cryptographic Schemes Provably as Secure as Subset Sum Russell Impagliazzo, Moni Naor |
| 1989 | Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry Bonnie Berger, John Rompel, Peter W. Shor |
| 1989 | Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary) Samir Khuller, Baruch Schieber |
| 1989 | Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version) Kieran T. Herley |
| 1989 | Efficient Tree Pattern Matching (Preliminary Version) S. Rao Kosaraju |
| 1989 | Ensemble Motion Planning in Trees Greg N. Frederickson, D. J. Guan |
| 1989 | Every Polynomial-Time 1-Degree Collapses iff P=PSPACE Stephen A. Fenner, Stuart A. Kurtz, James S. Royer |
| 1989 | Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies Frank Thomson Leighton, Bruce M. Maggs |
| 1989 | Fast Matching Algorithms for Points on a Polygon (Extended Abstract) Odile Marcotte, Subhash Suri |
| 1989 | Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract) Gary L. Miller, Joseph Naor |
| 1989 | Full Abstraction for Nondeterministic Dataflow Networks James R. Russell |
| 1989 | Galois Groups and Factoring Polynomials over Finite Fields Lajos Rónyai |
| 1989 | Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions Bettina Just |
| 1989 | Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results David Haussler |
| 1989 | Generating Random Spanning Trees Andrei Z. Broder |
| 1989 | Graph Products and Chromatic Numbers Nathan Linial, Umesh V. Vazirani |
| 1989 | How to Recycle Random Bits Russell Impagliazzo, David Zuckerman |
| 1989 | Incremental Planarity Testing (Extended Abstract) Giuseppe Di Battista, Roberto Tamassia |
| 1989 | Interior-Point Methods in Parallel Computation Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos |
| 1989 | Learning Binary Relations and Total Orders (Extended Abstract) Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire |
| 1989 | Lower Bounds for Algebraic Computation Trees with Integer Inputs Andrew Chi-Chih Yao |
| 1989 | Lower Bounds for Constant Depth Circuits in the Presence of Help Bits Jin-Yi Cai |
| 1989 | Lower Bounds for Pseudorandom Number Generators Michael Kharitonov, Andrew V. Goldberg, Moti Yung |
| 1989 | Lower Bounds for the Stable Marriage Problem and its Variants Cheng Ng |
| 1989 | Minimum Resource Zero-Knowledge Proofs (Extended Abstract) Joe Kilian, Silvio Micali, Rafail Ostrovsky |
| 1989 | Multiparty Communication Complexity Danny Dolev, Tomás Feder |
| 1989 | Multiparty Computation with Faulty Majority (Extended Announcement) Donald Beaver, Shafi Goldwasser |
| 1989 | Network Decomposition and Locality in Distributed Computation Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin |
| 1989 | On Obstructions in Relation to a Fixed Viewpoint Ketan Mulmuley |
| 1989 | On Reversal Complexity for Alternating Turing Machines (Extended Abstract) Maciej Liskiewicz, Krzysztof Lorys |
| 1989 | On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract) Alan Siegel |
| 1989 | On the Complexity of Fixed Parameter Problems (Extended Abstract) Karl R. Abrahamson, John A. Ellis, Michael R. Fellows, Manuel E. Mata |
| 1989 | On the Complexity of Learning From Counterexamples (Extended Abstract) Wolfgang Maass, György Turán |
| 1989 | On the Complexity of Space Bounded Interactive Proofs (Extended Abstract) Anne Condon, Richard J. Lipton |
| 1989 | On the Complexity of a Game Related to the Dictionary Problem Kurt Mehlhorn, Stefan Näher, Monika Rauch |
| 1989 | On the Computational Power of PP and +P Seinosuke Toda |
| 1989 | On the Network Complexity of Selection C. Greg Plaxton |
| 1989 | On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract) Cynthia Dwork, Larry J. Stockmeyer |
| 1989 | One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract) Russell Impagliazzo, Michael Luby |
| 1989 | Output-Sensitive Hidden Surface Removal Mark H. Overmars, Micha Sharir |
| 1989 | Pipelining Computations in a Tree of Processors (Preliminary Version) S. Rao Kosaraju |
| 1989 | Planning and Learning in Permutation Groups Amos Fiat, Shahar Moses, Adi Shamir, Ilan Shimshoni, Gábor Tardos |
| 1989 | Polynomial End-To-End Communication (Extended Abstract) Baruch Awerbuch, Yishay Mansour, Nir Shavit |
| 1989 | Power of Fast VLSI Models Is Insensitive to Wires' Thinness Gene Itkis, Leonid A. Levin |
| 1989 | Privacy and Communication Complexity Eyal Kushilevitz |
| 1989 | Probabilistic Communication Complexity of Boolean Relations (Extended Abstract) Ran Raz, Avi Wigderson |
| 1989 | Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani |
| 1989 | Randomized Search Trees Cecilia R. Aragon, Raimund Seidel |
| 1989 | Recursive *-Tree Parallel Data-Structure (Extended Abstract) Omer Berkman, Uzi Vishkin |
| 1989 | Simplification of Nested Radicals Susan Landau |
| 1989 | Simulating (log ^c n)-wise Independence in NC Bonnie Berger, John Rompel |
| 1989 | Solvability in Asynchronous Environments (Extended Abstract) Benny Chor, Lior Moscovici |
| 1989 | Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version) Michael T. Goodrich, S. Rao Kosaraju |
| 1989 | Space-efficient Static Trees and Graphs Guy Jacobson |
| 1989 | Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract) Pravin M. Vaidya |
| 1989 | Stable Maintenance of Point Set Triangulations in Two Dimensions Steven Fortune |
| 1989 | Structure in Locally Optimal Solutions (Extended Abstract) Mark W. Krentel |
| 1989 | Subquadratic Simulations of Circuits by Branching Programs Jin-Yi Cai, Richard J. Lipton |
| 1989 | Testing Permutation Polynomials (Extended Abstract) Joachim von zur Gathen |
| 1989 | The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality Leszek Pacholski, Wieslaw Szwast |
| 1989 | The Complexity of Approximating the Square Root (Extended Summary) Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1989 | The Equivalence and Learning of Probabilistic Automata (Extended Abstract) Wen-Guey Tzeng |
| 1989 | The Inverse of an Automorphism in Polynomial Time Matthew Dickerson |
| 1989 | The Parallel Complexity of the Subgraph Connectivity Problem Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis |
| 1989 | The Probabilistic Method Yields Deterministic Parallel Algorithms Rajeev Motwani, Joseph Naor, Moni Naor |
| 1989 | The Strength of Weak Learnability (Extended Abstract) Robert E. Schapire |
| 1989 | The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract) Tao Jiang |
| 1989 | The Weighted Majority Algorithm Nick Littlestone, Manfred K. Warmuth |
| 1989 | Towards Optimal Distributed Consensus (Extended Abstract) Piotr Berman, Juan A. Garay, Kenneth J. Perry |
| 1989 | Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem Rajamani Sundar |
| 1989 | Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract) Yehuda Afek, Eli Gafni, Moty Ricklin |
| 1989 | Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version) Greg N. Frederickson |