| 1976 | Complexity of Trie Index Construction (Extended Abstract) | Douglas Comer, Ravi Sethi |
| 1976 | An Algebraic Formulation of Knuthian Semantics | Laurian M. Chirica, David F. Martin |
| 1976 | Alternation | Ashok K. Chandra, Larry J. Stockmeyer |
| 1976 | Parenthesis Generators | Luc Boasson, Maurice Nivat |
| 1976 | On the Structure of Complete Sets: Almost Everywhere Complexity and Infinitely Often Speedup | Leonard Berman |
| 1976 | A Second Step toward the Polynomial Hierarchy | Theodore P. Baker, Alan L. Selman |
| 1976 | Self-Organizing Binary Search Trees | Brian Allen, J. Ian Munro |
| 1976 | Diophantine Complexity | Leonard M. Adleman, Kenneth L. Manders |
| 1975 | On the Complexity of Comparison Problems using Linear Functions (Preliminary Report) | Andrew Chi-Chih Yao |
| 1975 | The Effect of the Field of Constants on the Number of Multiplication | Shmuel Winograd |
| 1975 | Evaluating Relational Expressions with Dense and Sparse Arguments | Thomas G. Szymanski, Jeffrey D. Ullman |
| 1975 | Closest-Point Problems | Michael Ian Shamos, Dan Hoey |
| 1975 | A Grammatical Characterization of Exponential-Time Languages | William C. Rounds |
| 1975 | The Effect of Basis on Size of Boolean Expressions | Vaughan R. Pratt |
| 1975 | Minimean Optimality in Sorting Algorithms | Ira Pohl |
| 1975 | Information Theory and the Complexity of Switching Networks (Preliminary Version) | Nicholas Pippenger |
| 1975 | Bases for Chain-Complete Posets | George Markowsky, Barry K. Rosen |
| 1975 | Synchronization and Computing Capabilities of Linear Asynchronous Structures | Richard J. Lipton, Raymond E. Miller, Lawrence Snyder |
| 1975 | Polynomials with 0-1 Coefficients that Are Hard to Evaluate | Richard J. Lipton |
| 1975 | An Optimal Bound for Two Dimensional Bin Packing | Daniel J. Kleitman, Michael M. Krieger |
| 1975 | Decidability of Equivalence, Containment, Intersection, and Separability of Context-Free Languages (Extended Abstract) | Harry B. Hunt III, J. L. Rangel |
| 1975 | On Time versus Space and Related Problems | John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant |
| 1975 | A Note on Tape Bounds for SLA Language Processing | Juris Hartmanis, Leonard Berman |
| 1975 | Economy of Descriptions by Parsers, DPDA's, and PDA's | Matthew M. Geller, Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman |
| 1975 | An Application of Graph Coloring to Printed Circuit Testing (Working Paper) | M. R. Garey, David S. Johnson, Hing C. So |