| 1975 | A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions Wolfgang J. Paul |
| 1975 | A Generalization and Proof of the Aanderaa-Rosenberg Conjecture Ronald L. Rivest, Jean Vuillemin |
| 1975 | Algorithmic Aspects of Vertex Elimination Donald J. Rose, Robert Endre Tarjan |
| 1975 | Comparative Complexity of Grammar Forms Seymour Ginsburg, Nancy A. Lynch |
| 1975 | Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms Richard J. Lipton, David P. Dobkin |
| 1975 | Computability Concepts for Programming Language Semantics Herbert Egli, Robert L. Constable |
| 1975 | Degree-Languages, Polynomial Time Recognition, and the LBA Problem Detlef Wotschke |
| 1975 | Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version) Stephen A. Cook |
| 1975 | Four Models for the Analysis of Optimization of Program Control Structures Terrence W. Pratt |
| 1975 | Geometric Complexity Michael Ian Shamos |
| 1975 | Hashing Schemes for Extendible Arrays (Extended Arrays) Arnold L. Rosenberg, Larry J. Stockmeyer |
| 1975 | Intercalation Theorems for Tree Transducer Languages C. Raymond Perrault |
| 1975 | Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property Kellogg S. Booth, George S. Lueker |
| 1975 | Lower Bounds on the Size of Boolean Formulas: Preliminary Report Michael J. Fischer, Albert R. Meyer, Mike Paterson |
| 1975 | Node Listings for Reducible Flow Graphs Alfred V. Aho, Jeffrey D. Ullman |
| 1975 | On (Un)predictability of Formal Languages (Extended Abstract) Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 1975 | On Computing the Minima of Quadratic Forms (Preliminary Report) Andrew Chi-Chih Yao |
| 1975 | On Decomposing Languages Defined by Parallel Devices Sven Skyum |
| 1975 | On Non-linear Lower Bounds in Computational Complexity Leslie G. Valiant |
| 1975 | On the (Combinatorial) Structure of L Languages without Interactions Andrzej Ehrenfeucht, Grzegorz Rozenberg |
| 1975 | On the Complexity of Grammar and Related Problems Harry B. Hunt III, Thomas G. Szymanski |
| 1975 | On the Complexity of the Extended String-to-String Correction Problem Robert A. Wagner |
| 1975 | On the Validity and Complexity of Bounded Resolution Zvi Galil |
| 1975 | Optimal Code Generation for Expression Trees Alfred V. Aho, Stephen C. Johnson |
| 1975 | Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA William C. Rounds, Nancy Martin, Jack W. Carlyle, Michael A. Harrison |
| 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 Complexity of Control Structures and Data Structures Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo |
| 1975 | The Complexity of Parallel Evaluation of Linear Recurrence Laurent Hyafil, H. T. Kung |
| 1975 | The Optimal Fixedpoint of Recursive Programs Zohar Manna, Adi Shamir |
| 1975 | Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees Michael L. Fredman |
| 1975 | a Combinatorial Problem which is Complete in Polynomial Space Shimon Even, Robert Endre Tarjan |