| 1987 | On the Cunning Power of Cheating Verifiers: Some Observations about Zero Knowledge Proofs (Extended Abstract) | Yair Oren |
| 1987 | The Multiplicative Complexity of Quadratic Boolean Forms | Roland Mirwald, Claus-Peter Schnorr |
| 1987 | Determining Edge Connectivity in O(nm) | David W. Matula |
| 1987 | Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm (Extended Abstract) | Nick Littlestone |
| 1987 | Distributive Graph Algorithms-Global Solutions from Local Data | Nathan Linial |
| 1987 | Approximation Algorithms for Scheduling Unrelated Parallel Machines | Jan Karel Lenstra, David B. Shmoys, va Tardos |
| 1987 | Canonical Labeling of Regular Graphs in Linear Average Time | Ludek Kucera |
| 1987 | The Organization of Permutation Architectures with Bussed Interconnections (Extended Abstract) | Joe Kilian, Shlomo Kipnis, Charles E. Leiserson |
| 1987 | Improved Algorithms for Graph Four-Connectivity | Arkady Kanevsky, Vijaya Ramachandran |
| 1987 | Multiplicative complexity of polynomial multiplication over finite fields (Extended abstract) | Michael Kaminski, Nader H. Bshouty |
| 1987 | Bounded Time-Stamps (Extended Abstract) | Amos Israeli, Ming Li |
| 1987 | Exponential Lower Bounds for Finding Brouwer Fixed Points (Extended Abstract) | Michael D. Hirsch, Stephen A. Vavasis |
| 1987 | Threshold circuits of bounded depth | Andrs Hajnal, Wolfgang Maass, Pavel Pudlk, Mario Szegedy, Gyrgy Turn |
| 1987 | Complete and Incomplete Randomized NP Problems | Yuri Gurevich |
| 1987 | Incomparability in Parallel Computation | Vince Grolmusz, Prabhakar Ragde |
| 1987 | The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) | Dima Grigoriev, Marek Karpinski |
| 1987 | Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract) | Oded Goldreich, Yishay Mansour, Michael Sipser |
| 1987 | A New Parallel Algorithm for the Maximal Independent Set Problem | Mark K. Goldberg, Thomas H. Spencer |
| 1987 | An Output Sensitive Algorithm for Computing Visibility Graphs | Subir Kumar Ghosh, David M. Mount |
| 1987 | The Complexity of Parallel Comparison Merging | Mihly Gerb-Graus, Danny Krizanc |
| 1987 | A Parallel Algorithm for Finding a Separator in Planar Graphs | Hillel Gazit, Gary L. Miller |
| 1987 | Functional Decomposition of Polynomials | Joachim von zur Gathen, Dexter Kozen, Susan Landau |
| 1987 | Channel Routing of Multiterminal Nets | Shaodi Gao, Michael Kaufmann |
| 1987 | A Practical Scheme for Non-interactive Verifiable Secret Sharing | Paul Feldman |
| 1987 | On the Lower Envelope of Bivariate Functions and its Applications | Herbert Edelsbrunner, Jnos Pach, Jacob T. Schwartz, Micha Sharir |