| 1988 | Expressing Combinatorial Optimization Problems by Linear Programs (Extended Abstract) | Mihalis Yannakakis |
| 1988 | Random Instances of a Graph Coloring Problem Are Hard | Ramarathnam Venkatesan, Leonid A. Levin |
| 1988 | Geometry Helps in Matching (Extended Abstract) | Pravin M. Vaidya |
| 1988 | Two Infinite Sets of Primes with Fast Primality Tests | Janos Pintz, William L. Steiger, Endre Szemerdi |
| 1988 | A Tradeoff between Space and Efficiency for Routing Tables (Extended Abstract) | David Peleg, Eli Upfal |
| 1988 | Towards an Architecture-Independent Analysis of Parallel Algorithms (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | Optimization, Approximation, and Complexity Classes (Extended Abstract) | Christos H. Papadimitriou, Mihalis Yannakakis |
| 1988 | A Faster Strongly Polynominal Minimum Cost Flow Algorithm | James B. Orlin |
| 1988 | Competitive Algorithms for On-line Problems | Mark S. Manasse, Lyle A. McGeoch, Daniel Dominic Sleator |
| 1988 | More Analysis of Double Hashing | George S. Lueker, Mariko Molodowitch |
| 1988 | Linearity and Unprovability of Set Union Problem Strategies | Martin Loebl, Jaroslav Nesetril |
| 1988 | A Time-Randomness Tradeoff for Oblivious Routing (Extended Abstract) | Danny Krizanc, David Peleg, Eli Upfal |
| 1988 | Detecting Cycles in Dynamic Graphs in Polynomial Time (Preliminary Version) | S. Rao Kosaraju, Gregory F. Sullivan |
| 1988 | Relativized Polynominal Time Hierarchies Having Exactly K Levels | Ker-I Ko |
| 1988 | Lower Bounds on the Complexity of Graph Properties | Valerie King |
| 1988 | Founding Cryptography on Oblivious Transfer | Joe Kilian |
| 1988 | Learning in the Presence of Malicious Errors (Extended Abstract) | Michael J. Kearns, Ming Li |
| 1988 | A Randomized Parallel Branch-and-Bound Procedure | Richard M. Karp, Yanjun Zhang |
| 1988 | Randomized Algorithms and Pseudorandom Numbers | Howard J. Karloff, Prabhakar Raghavan |
| 1988 | Monotone Circuits for Connectivity Require Super-logarithmic Depth | Mauricio Karchmer, Avi Wigderson |
| 1988 | Implicit Representation of Graphs | Sampath Kannan, Moni Naor, Steven Rudich |
| 1988 | On the Power of White Pebbles (Extended Abstract) | Bala Kalyanasundaram, Georg Schnitger |
| 1988 | Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) | Mark Jerrum, Alistair Sinclair |
| 1988 | Polynomial Universal Traversing Sequences for Cycles Are Constructible (Extended Abstract) | Sorin Istrail |
| 1988 | On Different Modes of Communication (Extended Abstract) | Bernd Halstenberg, Rdiger Reischuk |