| 1988 | 29th Annual Symposium on Foundations of Computer Science, White Plains, New York, USA, 24-26 October 1988 |
| 1988 | A Deterministic View of Random Sampling and its Use in Geometry Bernard Chazelle, Joel Friedman |
| 1988 | A Fast Planar Partition Algorithm, I (Extended Abstract) Ketan Mulmuley |
| 1988 | A Faster PSPACE Algorithm for Deciding the Existential Theory of the Reals James Renegar |
| 1988 | A Las Vegas Algorithm for Linear Programming When the Dimension Is Small Kenneth L. Clarkson |
| 1988 | A Lower Bound for Matrix Multiplication Nader H. Bshouty |
| 1988 | Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract) Claude Crépeau, Joe Kilian |
| 1988 | An Approximate Max-Flow Min-Cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms Frank Thomson Leighton, Satish Rao |
| 1988 | An Optimal Algorithm for Intersecting Line Segments in the Plane Bernard Chazelle, Herbert Edelsbrunner |
| 1988 | Bounds on the Cover Time (Preliminary Version) Andrei Z. Broder, Anna R. Karlin |
| 1988 | Combinatorial Algorithms for the Generalized Circulation Problem Andrew V. Goldberg, Serge A. Plotkin, Éva Tardos |
| 1988 | Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl |
| 1988 | Computing with Polynomials Given By Black Boxes for Their Evaluation: Greatest Common Divisors, Factorization, Separation of Numerators and Denominators Erich L. Kaltofen, Barry M. Trager |
| 1988 | Constructive Results from Graph Minors: Linkless Embeddings Rajeev Motwani, Arvind Raghunathan, Huzur Saran |
| 1988 | Coordinated Traversal: (t + 1)-Round Byzantine Agreement in Polynomial Time Yoram Moses, Orli Waarts |
| 1988 | Covering Polygons Is Hard (Preliminary Abstract) Joseph C. Culberson, Robert A. Reckhow |
| 1988 | Dynamic Networks Are as Fast as Static Networks (Preliminary Version) Baruch Awerbuch, Michael Sipser |
| 1988 | Dynamic Perfect Hashing: Upper and Lower Bounds Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan |
| 1988 | Effect of Connectivity in Associative Memory Models (Preliminary Version) János Komlós, Ramamohan Paturi |
| 1988 | Efficient Parallel Algorithms for Chordal Graphs Philip N. Klein |
| 1988 | Fast Management of Permutation Groups László Babai, Eugene M. Luks, Ákos Seress |
| 1988 | Fully Abstract Models of the Lazy Lambda Calculus C.-H. Luke Ong |
| 1988 | Fully Dynamic Techniques for Point Location and Transitive Closure in Planar Structures (Extended Abstract) Franco P. Preparata, Roberto Tamassia |
| 1988 | Genus g Graphs have Pagenumber O(sqrt(g)) Seth M. Malitz |
| 1988 | Hardness vs. Randomness (Extended Abstract) Noam Nisan, Avi Wigderson |
| 1988 | Homogeneous Measures and Polynomial Time Invariants Leonid A. Levin |
| 1988 | Increasing the Size of a Network by a Constant Factor Can Increase Performance by More Than a Constant Factor Richard A. Koch |
| 1988 | Lattices, Möbius Functions and Communication Complexity László Lovász, Michael E. Saks |
| 1988 | Learning Probabilistic Prediction Functions (Extended Abstract) Alfredo De Santis, George Markowsky, Mark N. Wegman |
| 1988 | Learning via Queries William I. Gasarch, Carl H. Smith |
| 1988 | Lower Bounds for Integer Greatest Common Divisor Computations (Extended Summary) Yishay Mansour, Baruch Schieber, Prasoon Tiwari |
| 1988 | Near-Optimal Time-Space Tradeoff for Element Distinctness Andrew Chi-Chih Yao |
| 1988 | New Algorithms for Finding Irreducible Polynomials over Finite Fields Victor Shoup |
| 1988 | New upper bounds in Klee's measure problem (extended abstract) Mark H. Overmars, Chee-Keng Yap |
| 1988 | Nonexpressibility of Fairness and Signaling David A. McAllester, Prakash Panangaden, Vasant Shanbhogue |
| 1988 | Notes on Searching in Multidimensional Monotone Arrays (Preliminary Version) Alok Aggarwal, James K. Park |
| 1988 | On Pointers versus Addresses (Extended Abstract) Amir M. Ben-Amram, Zvi Galil |
| 1988 | On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract) Lenore Blum, Mike Shub, Steve Smale |
| 1988 | On the Complexity of Kinodynamic Planning John F. Canny, Bruce Randall Donald, John H. Reif, Patrick G. Xavier |
| 1988 | On the Complexity of omega-Automata Shmuel Safra |
| 1988 | On the Effects of Feedback in Dynamic Network Protocols (Preliminary Version) Baruch Awerbuch |
| 1988 | On the Existence of Pseudorandom Generators (Extended Abstract) Oded Goldreich, Hugo Krawczyk, Michael Luby |
| 1988 | Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs Elias Dahlhaus, Péter Hajnal, Marek Karpinski |
| 1988 | Parallel Comparison Algorithms for Approximation Problems Noga Alon, Yossi Azar |
| 1988 | Polynomial Algorithm for the k-Cut Problem Olivier Goldschmidt, Dorit S. Hochbaum |
| 1988 | Polytopes, Permanents and Graphs with Large Factors Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani |
| 1988 | Predicting {0,1}-Functions on Randomly Drawn Points (Extended Abstract) David Haussler, Nick Littlestone, Manfred K. Warmuth |
| 1988 | Reachability Is Harder for Directed than for Undirected Finite Graphs (Preliminary Version) Miklós Ajtai, Ronald Fagin |
| 1988 | Removing Randomness in Parallel Computation Without a Processor Penalty Michael Luby |
| 1988 | Results on learnability and the Vapnik-Chervonenkis dimension (Extended Abstract) Nathan Linial, Yishay Mansour, Ronald L. Rivest |
| 1988 | Speeding up Dynamic Programming David Eppstein, Zvi Galil, Raffaele Giancarlo |
| 1988 | Sublinear-Time Parallel Algorithms for Matching and Related Problems Andrew V. Goldberg, Serge A. Plotkin, Pravin M. Vaidya |
| 1988 | Take a Walk, Grow a Tree (Preliminary Version) Sandeep N. Bhatt, Jin-Yi Cai |
| 1988 | The Complexity of Tree Automata and Logics of Programs (Extended Abstract) E. Allen Emerson, Charanjit S. Jutla |
| 1988 | The Complexity of the Pigeonhole Principle Miklós Ajtai |
| 1988 | The Influence of Variables on Boolean Functions (Extended Abstract) Jeff Kahn, Gil Kalai, Nathan Linial |
| 1988 | Three Stacks Michael L. Fredman, Deborah L. Goldsmith |
| 1988 | Universal Packet Routing Algorithms (Extended Abstract) Frank Thomson Leighton, Bruce M. Maggs, Satish Rao |
| 1988 | Verifying Temporal Properties of Finite-State Probabilistic Programs Costas Courcoubetis, Mihalis Yannakakis |
| 1988 | Zero-knowledge with Log-Space Verifiers Joe Kilian |