default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID16th 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
Session II
- 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
Session III
- 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
Session IV
- 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
Session V
- 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-05 22:23 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
