16. FOCS 1975:
Berkeley,
California
16th Annual Symposium on Foundations of Computer Science,
Berkeley, California, 13-15 October 1975. IEEE Computer Society
- Shmuel Winograd:
The Effect of the Field of Constants on the Number of Multiplication.
1-2
- Robert W. Floyd:
The Exact Time Required to Perform Generalized Addition.
3-5
- Richard J. Lipton:
Polynomials with 0-1 Coefficients that Are Hard to Evaluate.
6-10
- L. Csanky:
Fast Parallel Matrix Inversion Algorithms.
11-12
- Eshrat Arjomandi, Derek G. Corneil:
Parallel Computations in Graph Theory.
13-18
- Richard J. Lipton, Raymond E. Miller, Lawrence Snyder:
Synchronization and Computing Capabilities of Linear Asynchronous Structures.
19-28
- J. W. de Bakker:
Flow of Control in the Proof Theory of Structured Programming.
29-33
- George Markowsky, Barry K. Rosen:
Bases for Chain-Complete Posets.
34-47
- Peter J. Downey, Ravi Sethi:
Correct Computation Rules for Recursive Languages (Extended Abstract).
48-56
- John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant:
On Time versus Space and Related Problems.
57-64
- Juris Hartmanis, Leonard Berman:
A Note on Tape Bounds for SLA Language Processing.
65-70
- Ira Pohl:
Minimean Optimality in Sorting Algorithms.
71-74
- Peter van Emde Boas:
Preserving Order in a Forest in less than Logarithmic Time.
75-84
- Andrew Chi-Chih Yao:
On the Complexity of Comparison Problems using Linear Functions (Preliminary Report).
85-89
- Thomas G. Szymanski, Jeffrey D. Ullman:
Evaluating Relational Expressions with Dense and Sparse Arguments.
90-97
- Michael L. Fredman:
On the Decision Tree Complexity of the Shortest Path Problems.
98-99
- Shimon Even, Oded Kariv:
An O(n^2.5) Algorithm for Maximum Matching in General Graphs.
100-112
- Nicholas Pippenger:
Information Theory and the Complexity of Switching Networks (Preliminary Version).
113-118
- Vaughan R. Pratt:
The Effect of Basis on Size of Boolean Expressions.
119-121
- Matthew M. Geller, Harry B. Hunt III, Thomas G. Szymanski, Jeffrey D. Ullman:
Economy of Descriptions by Parsers, DPDA's, and PDA's.
122-127
- Catriel Beeri:
An Improvement of Valiant's Decision Procedure for Equivalence of Deterministic Finite-Turn Pushdown Automata.
128-134
- William C. Rounds:
A Grammatical Characterization of Exponential-Time Languages.
135-143
- Harry B. Hunt III, J. L. Rangel:
Decidability of Equivalence, Containment, Intersection, and Separability of Context-Free Languages (Extended Abstract).
144-150
- Michael Ian Shamos, Dan Hoey:
Closest-Point Problems.
151-162
- Daniel J. Kleitman, Michael M. Krieger:
An Optimal Bound for Two Dimensional Bin Packing.
163-168
- Leonard M. Adleman, Kenneth L. Manders:
Computational Complexity of Decision Procedures for Polynomials (Extended Abstract).
169-177
- M. R. Garey, David S. Johnson, H. C. So:
An Application of Graph Coloring to Printed Circuit Testing (Working Paper).
178-183
- Shimon Even, Alon Itai, Adi Shamir:
On the Complexity of Timetable and Multi-Commodity Flow Problems.
184-193
Copyright © Mon Nov 2 20:36:40 2009
by Michael Ley (ley@uni-trier.de)
