7. STOC 1975: Albuquerque, New Mexico, USA

• 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
  
• Andrzej Ehrenfeucht, Grzegorz Rozenberg:
  On the (Combinatorial) Structure of L Languages without Interactions. 137-144
  
• 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
  

Last update Fri May 25 08:42:06 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page