21. FOCS 1980: Syracuse, New York, USA

Session I

• Richard M. Karp, Christos H. Papadimitriou:
  On Linear Characterizations of Combinatorial Optimization Problems. 1-9
  
• Mihalis Yannakakis:
  On a Class of Totally Unimodular Matrices. 10-16
  
• Silvio Micali, Vijay V. Vazirani:
  An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs. 17-27
  
• T. C. Hu, M. T. Shing:
  Some Theorems about Matrix Multiplication (Extended Abstract). 28-35
  
• Merrick L. Furst, John E. Hopcroft, Eugene M. Luks:
  Polynomial-Time Algorithms for Permutation Groups. 36-41
  
• Eugene M. Luks:
  Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time. 42-49
  
• Barbara Simons:
  A Fast Algorithm for Multiprocessor Scheduling. 50-53
  

Session II

• Stephen R. Mahaney:
  Sparse Complete Sets for NP: Solution of a Conjecture of Berman and Hartmanis. 54-60
  
• Ivan Hal Sudborough:
  Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes. 62-73
  
• Neil Immerman:
  Upper and Lower Bounds for First Order Expressibility. 74-82
  
• Eitan M. Gurari:
  The Equivalence Problem for Deterministic Two-Way Sequential Transducers Is Decidable. 83-85
  
• Gary L. Peterson:
  Succinct Representation, Random Strings, and Complexity Classes. 86-95
  

Session III

• Gérard P. Huet, Jean-Marie Hullot:
  Proofs by Induction in Equational Theories with Constructors. 96-107
  
• Paul Chew:
  An Improved Algorithm for Computing With Equations. 108-117
  
• Robert L. Constable:
  Programs and Types. 118-128
  
• David Harel, Dexter Kozen, Rohit Parikh:
  Process Logic: Expressiveness, Decidability, Completeness. 129-142
  
• Nissim Francez, Daniel J. Lehmann, Amir Pnueli:
  A Linear History Semantics for Distributed Languages (Extended Abstract). 143-151
  
• Harry B. Hunt III, Daniel J. Rosenkrantz:
  The Complexity of Recursion Schemes and Recursive Programming Languages (Extended Abstract). 152-160
  
• Bruno Courcelle, Paul Franchi-Zannettacci:
  On the Expressive Power of Attribute Grammars. 161-172
  
• A. J. Kfoury:
  Loop Elimination and Loop Reduction-A Model-Theoretic Analysis of Programs (Partial Report). 173-184
  
• Neil D. Jones, Steven S. Muchnick:
  Complexity of Flow Analysis, Inductive Assertion Synthesis and a Language Due to Dijkstra. 185-190
  

Session IV

• Michael L. Fredman:
  The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries. 191-199
  
• David P. Dobkin, J. Ian Munro:
  Efficient Uses of the Past. 200-206
  
• Philippe Flajolet, Andrew M. Odlyzko:
  Exploring Binary Trees and Other Simple Trees. 207-216
  
• Jon Louis Bentley, Donna J. Brown:
  A General Class of Resource Tradeoffs (Extended Abstract). 217-228
  
• Ernst-Erich Doberkat:
  Some Observations on the Average Behavior of Heapsort (Preliminary Report). 229-237
  
• Jeffrey Scott Vitter:
  Tuning the Coalesced Hashing Method to Obtain Optimum Performance (Detailed Abstract). 238-247
  
• Samuel W. Bent, Daniel Dominic Sleator, Robert Endre Tarjan:
  Biased 2-3 Trees. 248-254
  
• Greg N. Frederickson:
  Implicit Data Structures with Fast Update (Preliminary Report). 255-259
  

Session V

• Robert W. Floyd, Jeffrey D. Ullman:
  The Compilation of Regular Expressions into Integrated Circuits (Extended Abstract). 260-269
  
• Charles E. Leiserson:
  Area-Efficient Graph Layouts (for VLSI). 270-281
  
• Andrea S. LaPaugh:
  A Polynomial Time Algorithm for Optimal Routing around a Rectangle (Extended Abstract). 282-293
  
• Jean Vuillemin:
  A Combinatorial Limit to the Computing Power of V.L.S.I. Circuits (Extended Abstract). 294-300
  
• F. Frances Yao:
  On the Priority Approach to Hidden-Surface Algorithms (Preliminary Report). 301-307
  
• Dov Harel:
  A Linear Time Algorithm for the Lowest Common Ancestors Problem (Extended Abstract). 308-319
  
• Mark N. Wegman:
  Parsing for Structural Editors (Extended Abstract). 320-327
  
• Mihalis Yannakakis, Christos H. Papadimitriou:
  Algebraic Dependencies (Extended Abstract). 328-332
  
• Ashok K. Chandra, David Harel:
  Structure and Complexity of Relational Queries. 333-347
  

Session VI

• Jia-Wei Hong:
  On Similarity and Duality of Computation (Extended Abstract). 348-359
  
• Patrick W. Dymond, Stephen A. Cook:
  Hardware Complexity and Parallel Computation (Preliminary Version). 360-372
  
• Nissim Francez, Michael Rodeh:
  A Distributed Abstract Data Type Implemented by a Probabilistic Communication Scheme. 373-379
  
• Gilles Brassard:
  A Time-Luck Tradeoff in Cryptography. 380-386
  
• Leonard M. Adleman:
  On Distinguishing Prime Numbers from Composite Numbers (Abstract). 387-406
  
• Michael O. Rabin:
  N-Process Synchronization by 4 log _2 N-Valued Shared Variables. 407-410
  

Late Paper

• Burchard von Braunmühl, Rutger Verbeek:
  A Recognition Algorithm for Deterministic CFLS optimal in Time and Space. 411-420
  

Last update Wed May 23 00:46:55 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page