16. FOCS 1975: Berkeley, California, USA

16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975. IEEE Computer Society 1975

Session I

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

Last update Fri May 25 08:14:14 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page