| 1988 | Effect of Connectivity in Associative Memory Models (Preliminary Version) | Jnos Komls, Ramamohan Paturi |
| 1988 | Increasing the Size of a Network by a Constant Factor Can Increase Performance by More Than a Constant Factor | Richard A. Koch |
| 1988 | Efficient Parallel Algorithms for Chordal Graphs | Philip N. Klein |
| 1988 | Zero-knowledge with Log-Space Verifiers | Joe Kilian |
| 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 | The Influence of Variables on Boolean Functions (Extended Abstract) | Jeff Kahn, Gil Kalai, Nathan Linial |
| 1988 | Predicting {0,1}-Functions on Randomly Drawn Points (Extended Abstract) | David Haussler, Nick Littlestone, Manfred K. Warmuth |
| 1988 | Polynomial Algorithm for the k-Cut Problem | Olivier Goldschmidt, Dorit S. Hochbaum |
| 1988 | On the Existence of Pseudorandom Generators (Extended Abstract) | Oded Goldreich, Hugo Krawczyk, Michael Luby |
| 1988 | Sublinear-Time Parallel Algorithms for Matching and Related Problems | Andrew V. Goldberg, Serge A. Plotkin, Pravin M. Vaidya |
| 1988 | Combinatorial Algorithms for the Generalized Circulation Problem | Andrew V. Goldberg, Serge A. Plotkin, va Tardos |
| 1988 | Learning via Queries | William I. Gasarch, Carl H. Smith |
| 1988 | Three Stacks | Michael L. Fredman, Deborah L. Goldsmith |
| 1988 | Speeding up Dynamic Programming | David Eppstein, Zvi Galil, Raffaele Giancarlo |
| 1988 | The Complexity of Tree Automata and Logics of Programs (Extended Abstract) | E. Allen Emerson, Charanjit S. Jutla |
| 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 | Learning Probabilistic Prediction Functions (Extended Abstract) | Alfredo De Santis, George Markowsky, Mark N. Wegman |
| 1988 | Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs | Elias Dahlhaus, Pter Hajnal, Marek Karpinski |
| 1988 | Polytopes, Permanents and Graphs with Large Factors | Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani |
| 1988 | Covering Polygons Is Hard (Preliminary Abstract) | Joseph C. Culberson, Robert A. Reckhow |
| 1988 | Achieving Oblivious Transfer Using Weakened Security Assumptions (Extended Abstract) | Claude Crpeau, Joe Kilian |
| 1988 | Verifying Temporal Properties of Finite-State Probabilistic Programs | Costas Courcoubetis, Mihalis Yannakakis |
| 1988 | Combinatorial Complexity Bounds for Arrangements of Curves and Surfaces | Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Emo Welzl |
| 1988 | A Las Vegas Algorithm for Linear Programming When the Dimension Is Small | Kenneth L. Clarkson |
| 1988 | A Deterministic View of Random Sampling and its Use in Geometry | Bernard Chazelle, Joel Friedman |