| 1975 | Geometric Complexity | Michael Ian Shamos |
| 1975 | Algorithmic Aspects of Vertex Elimination | Donald J. Rose, Robert Endre Tarjan |
| 1975 | Hashing Schemes for Extendible Arrays (Extended Arrays) | Arnold L. Rosenberg, Larry J. Stockmeyer |
| 1975 | A Generalization and Proof of the Aanderaa-Rosenberg Conjecture | Ronald L. Rivest, Jean Vuillemin |
| 1975 | Four Models for the Analysis of Optimization of Program Control Structures | Terrence W. Pratt |
| 1975 | Intercalation Theorems for Tree Transducer Languages | C. Raymond Perrault |
| 1975 | A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions | Wolfgang J. Paul |
| 1975 | Proving Assertions about Programs that Manipulate Data Structures | Derek C. Oppen, Stephen A. Cook |
| 1975 | Riemann's Hypothesis and Tests for Primality | Gary L. Miller |
| 1975 | The Optimal Fixedpoint of Recursive Programs | Zohar Manna, Adi Shamir |
| 1975 | The Complexity of Control Structures and Data Structures | Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo |
| 1975 | Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms | Richard J. Lipton, David P. Dobkin |
| 1975 | The Complexity of Parallel Evaluation of Linear Recurrence | Laurent Hyafil, H. T. Kung |
| 1975 | On the Complexity of Grammar and Related Problems | Harry B. Hunt III, Thomas G. Szymanski |
| 1975 | Comparative Complexity of Grammar Forms | Seymour Ginsburg, Nancy A. Lynch |
| 1975 | On the Validity and Complexity of Bounded Resolution | Zvi Galil |
| 1975 | Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees | Michael L. Fredman |
| 1975 | Lower Bounds on the Size of Boolean Formulas: Preliminary Report | Michael J. Fischer, Albert R. Meyer, Mike Paterson |
| 1975 | a Combinatorial Problem which is Complete in Polynomial Space | Shimon Even, Robert Endre Tarjan |
| 1975 | On the (Combinatorial) Structure of L Languages without Interactions | Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 1975 | On (Un)predictability of Formal Languages (Extended Abstract) | Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 1975 | Computability Concepts for Programming Language Semantics | Herbert Egli, Robert L. Constable |
| 1975 | Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version) | Stephen A. Cook |
| 1975 | Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property | Kellogg S. Booth, George S. Lueker |
| 1975 | Node Listings for Reducible Flow Graphs | Alfred V. Aho, Jeffrey D. Ullman |