| 1975 | 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975 |
| 1975 | A Grammatical Characterization of Exponential-Time Languages William C. Rounds |
| 1975 | A Note on Tape Bounds for SLA Language Processing Juris Hartmanis, Leonard Berman |
| 1975 | An Application of Graph Coloring to Printed Circuit Testing (Working Paper) M. R. Garey, David S. Johnson, Hing C. So |
| 1975 | An Improvement of Valiant's Decision Procedure for Equivalence of Deterministic Finite-Turn Pushdown Automata Catriel Beeri |
| 1975 | An O(n^2.5) Algorithm for Maximum Matching in General Graphs Shimon Even, Oded Kariv |
| 1975 | An Optimal Bound for Two Dimensional Bin Packing Daniel J. Kleitman, Michael M. Krieger |
| 1975 | Bases for Chain-Complete Posets George Markowsky, Barry K. Rosen |
| 1975 | Closest-Point Problems Michael Ian Shamos, Dan Hoey |
| 1975 | Computational Complexity of Decision Procedures for Polynomials (Extended Abstract) Leonard M. Adleman, Kenneth L. Manders |
| 1975 | Correct Computation Rules for Recursive Languages (Extended Abstract) Peter J. Downey, Ravi Sethi |
| 1975 | Decidability of Equivalence, Containment, Intersection, and Separability of Context-Free Languages (Extended Abstract) Harry B. Hunt III, J. L. Rangel |
| 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 | Evaluating Relational Expressions with Dense and Sparse Arguments Thomas G. Szymanski, Jeffrey D. Ullman |
| 1975 | Fast Parallel Matrix Inversion Algorithms L. Csanky |
| 1975 | Flow of Control in the Proof Theory of Structured Programming J. W. de Bakker |
| 1975 | Information Theory and the Complexity of Switching Networks (Preliminary Version) Nicholas Pippenger |
| 1975 | Minimean Optimality in Sorting Algorithms Ira Pohl |
| 1975 | On Time versus Space and Related Problems John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant |
| 1975 | On the Complexity of Comparison Problems using Linear Functions (Preliminary Report) Andrew Chi-Chih Yao |
| 1975 | On the Complexity of Timetable and Multi-Commodity Flow Problems Shimon Even, Alon Itai, Adi Shamir |
| 1975 | On the Decision Tree Complexity of the Shortest Path Problems Michael L. Fredman |
| 1975 | Parallel Computations in Graph Theory Eshrat Arjomandi, Derek G. Corneil |
| 1975 | Polynomials with 0-1 Coefficients that Are Hard to Evaluate Richard J. Lipton |
| 1975 | Preserving Order in a Forest in less than Logarithmic Time Peter van Emde Boas |
| 1975 | Synchronization and Computing Capabilities of Linear Asynchronous Structures Richard J. Lipton, Raymond E. Miller, Lawrence Snyder |
| 1975 | The Effect of Basis on Size of Boolean Expressions Vaughan R. Pratt |
| 1975 | The Effect of the Field of Constants on the Number of Multiplication Shmuel Winograd |
| 1975 | The Exact Time Required to Perform Generalized Addition Robert W. Floyd |