| 1988 | How to Sign Given Any Trapdoor Function (Extended Abstract) | Mihir Bellare, Silvio Micali |
| 1988 | Energy Consumption in VLSI Circuits (Preliminary Version) | Alok Aggarwal, Ashok K. Chandra, Prabhakar Raghavan |
| 1988 | Virtual Memory Algorithms (Preliminary Version) | Alok Aggarwal, Ashok K. Chandra |
| 1988 | Using Smoothness to Achieve Parallelism (Abstract) | Leonard M. Adleman, Kireeti Kompella |
| 1987 | Properties that Characterize LOGCFL | H. Venkateswaran |
| 1987 | Efficiency Considerations in Using Semi-random Sources (Extended Abstract) | Umesh V. Vazirani |
| 1987 | An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations | Pravin M. Vaidya |
| 1987 | Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity | Roman Smolensky |
| 1987 | Threshold Spectra for Random Graphs | Saharon Shelah, Joel Spencer |
| 1987 | Simple Algebras Are Difficult | Lajos Rnyai |
| 1987 | Constructing Disjoint Paths on Expander Graphs (Extended Abstract) | David Peleg, Eli Upfal |
| 1987 | On Learning Boolean Functions | B. K. Natarajan |
| 1987 | Fast Parallel Algorithms for Chordal Graphs (Extended Abstract) | Joseph Naor, Moni Naor, Alejandro A. Schffer |
| 1987 | Searching a Two Key Table Under a Single Key | J. Ian Munro |
| 1987 | Matching Is as Easy as Matrix Inversion | Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani |
| 1987 | Dynamic Parallel Complexity of Computational Circuits | Gary L. Miller, Shang-Hua Teng |
| 1987 | A New Graph Triconnectivity Algorithm and Its Parallelization | Gary L. Miller, Vijaya Ramachandran |
| 1987 | Two Tapes Are Better than One for Off-Line Turing Machines | Wolfgang Maass, Georg Schnitger, Endre Szemerdi |
| 1987 | Imperfect Random Sources and Discrete Controlled Processes | David Lichtenstein, Nathan Linial, Michael E. Saks |
| 1987 | The Decision Problem for the Probabilities of Higher-Order Properties | Phokion G. Kolaitis, Moshe Y. Vardi |
| 1987 | On the Learnability of Boolean Formulae | Michael J. Kearns, Ming Li, Leonard Pitt, Leslie G. Valiant |
| 1987 | Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials | Erich L. Kaltofen |
| 1987 | Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract) | Kazuo Iwano, Kenneth Steiglitz |
| 1987 | The Strong Exponential Hierarchy Collapses | Lane A. Hemachandra |
| 1987 | The Pagenumber of Genus g Graphs is O(g) | Lenwood S. Heath, Sorin Istrail |