 |
 |
Proceedings of the 7th Annual ACM Symposium on Theory of Computing, May 5-7, 1975, Albuquerque, New Mexico, USA. ACM 1975
- Richard J. Lipton, David P. Dobkin:
Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials, and n-linear Forms.
1-5
- Ronald L. Rivest, Jean Vuillemin:
A Generalization and Proof of the Aanderaa-Rosenberg Conjecture.
6-11
- Laurent Hyafil, H. T. Kung:
The Complexity of Parallel Evaluation of Linear Recurrence.
12-22
- Andrew Chi-Chih Yao:
On Computing the Minima of Quadratic Forms (Preliminary Report).
23-26
- Wolfgang J. Paul:
A 2.5 n-lower Bound on the Combinatorial Complexity of Boolean Functions.
27-36
- Michael J. Fischer, Albert R. Meyer, Mike Paterson:
Lower Bounds on the Size of Boolean Formulas: Preliminary Report.
37-44
- Leslie G. Valiant:
On Non-linear Lower Bounds in Computational Complexity.
45-53
- Harry B. Hunt III, Thomas G. Szymanski:
On the Complexity of Grammar and Related Problems.
54-65
- Shimon Even, Robert Endre Tarjan:
a Combinatorial Problem which is Complete in Polynomial Space.
66-71
- Zvi Galil:
On the Validity and Complexity of Bounded Resolution.
72-82
- Stephen A. Cook:
Feasibly Constructive Proofs and the Propositional Calculus (Preliminary Version).
83-97
- Herbert Egli, Robert L. Constable:
Computability Concepts for Programming Language Semantics.
98-106
- Derek C. Oppen, Stephen A. Cook:
Proving Assertions about Programs that Manipulate Data Structures.
107-116
- Andrzej Ehrenfeucht, Grzegorz Rozenberg:
On (Un)predictability of Formal Languages (Extended Abstract).
117-120
- Sven Skyum:
On Decomposing Languages Defined by Parallel Devices.
121-125
- C. Raymond Perrault:
Intercalation Theorems for Tree Transducer Languages.
126-136
- Detlef Wotschke:
Degree-Languages, Polynomial Time Recognition, and the LBA Problem.
145-152
- Seymour Ginsburg, Nancy A. Lynch:
Comparative Complexity of Grammar Forms.
153-158
- Arnold L. Rosenberg, Larry J. Stockmeyer:
Hashing Schemes for Extendible Arrays (Extended Arrays).
159-166
- Terrence W. Pratt:
Four Models for the Analysis of Optimization of Program Control Structures.
167-176
- Alfred V. Aho, Jeffrey D. Ullman:
Node Listings for Reducible Flow Graphs.
177-185
- Richard J. Lipton, Stanley C. Eisenstat, Richard A. DeMillo:
The Complexity of Control Structures and Data Structures.
186-193
- Zohar Manna, Adi Shamir:
The Optimal Fixedpoint of Recursive Programs.
194-206
- Alfred V. Aho, Stephen C. Johnson:
Optimal Code Generation for Expression Trees.
207-217
- Robert A. Wagner:
On the Complexity of the Extended String-to-String Correction Problem.
218-223
- Michael Ian Shamos:
Geometric Complexity.
224-233
- Gary L. Miller:
Riemann's Hypothesis and Tests for Primality.
234-239
- Michael L. Fredman:
Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees.
240-244
- Donald J. Rose, Robert Endre Tarjan:
Algorithmic Aspects of Vertex Elimination.
245-254
- Kellogg S. Booth, George S. Lueker:
Linear Algorithms to Recognize Interval Graphs and Test for the Consecutive Ones Property.
255-265
Copyright © Mon Nov 2 21:15:19 2009
by Michael Ley (ley@uni-trier.de)