20. FOCS 1979: San Juan, Puerto Rico

Session I

• Yechiam Yemini:
  Some Theoretical Aspects of Position-Location Problems. 1-8
  
• David P. Dobkin, Lawrence Snyder:
  On a General Method for Maximizing and Minimizing among Certain Geometric Problems (Extended Abstract). 9-17
  
• David G. Kirkpatrick:
  Efficient Computation of Continuous Skeletons. 18-27
  
• Victor Y. Pan:
  Field Extension and Triangular Aggregating, Uniting and Canceling for the Acceleration of Matrix Multiplications. 28-38
  
• László Babai, Ludek Kucera:
  Canonical Labelling of Graphs in Linear Average Time. 39-46
  
• J. C. Lagarias:
  Succinct Certificates for the Solvability of Binary Quadratic Diophantine Equations. 47-54
  
• Leonard M. Adleman:
  A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography (Abstract). 55-60
  
• Nicholas Pippenger:
  Computational Complexity in Algebraic Function Fields (Preliminary Version). 61-65
  

Session II

• Sheila A. Greibach:
  Formal Languages: Origins and Directions. 66-90
  
• Meera Blattner:
  The Decidability of the Equivalence of Context-Free Grammar Forms. 91-96
  
• Hermann A. Maurer, Maurice Nivat:
  Bijective A-Transducers. 97-100
  
• Dexter Kozen:
  Semantics of Probabilistic Programs. 101-114
  
• Vaughan R. Pratt:
  Models of Program Logics. 115-122
  
• Nachum Dershowitz:
  Orderings for Term-Rewriting Systems. 123-131
  
• Karl J. Lieberherr, Ernst Specker:
  Complexity of Partial Satisfaction. 132-139
  

Session III

• Franco P. Preparata, Jean Vuillemin:
  The Cube-Connected-Cycles: A Versatile Network for Parallel Computation (Extended Abstract). 140-147
  
• James B. Saxe, Jon Louis Bentley:
  Transforming Static Data Structures to Dynamic Structures (Abridged Version). 148-168
  
• Gaston H. Gonnet, J. Ian Munro, Hendra Suwanda:
  Toward Self-Organizing Linear Search (Preliminary Draught). 169-174
  
• Mark N. Wegman, Larry Carter:
  New Classes and Applications of Hash Functions. 175-182
  
• Philippe Flajolet, Jean Françon, Jean Vuillemin:
  Towards Analysing Sequences of Operations for Dynamic Data Structures (Preliminary Version). 183-195
  
• Harold N. Gabow, Robert Endre Tarjan:
  Efficient Algorithms for Simple Matroid Intersection Problems. 196-204
  
• Bengt Aspvall, Yossi Shiloach:
  A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables per Inequality. 205-217
  
• Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff:
  Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. 218-223
  

Session IV

• Juris Hartmanis:
  Observations about the Development of Theoretical Computer Science. 224-233
  
• Michael J. Fischer, Nancy A. Lynch, James E. Burns, Allan Borodin:
  Resource Allocation with Immunity to Limited Process Failure (Preliminary Report). 234-254
  
• Edmund M. Clarke, Lishing Liu:
  Approximate Algorithms for Optimization of Busy Waiting in Parallel Programs (Preliminary Report). 255-266
  
• Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis:
  Modeling Communications Protocols by Automata. 267-273
  
• Zvi M. Kedem, Abraham Silberschatz:
  Controlling Concurrency Using Locking Protocols (Preliminary Report). 274-285
  
• Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung:
  Locking Policies: Safety and Freedom from Deadlock. 286-297
  

Session V

• Wolfgang J. Paul, Rüdiger Reischuk:
  On Time versus Space II. 298-306
  
• Nicholas Pippenger:
  On Simultaneous Resource Bounds (Preliminary Version). 307-311
  
• Walter L. Ruzzo:
  On Uniform Circuit Complexity (Extended Abstract). 312-318
  
• Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, Martin Tompa:
  A Time-Space Tradeoff for Sorting on Non-Oblivious Machines. 319-327
  
• Richard Schroeppel, Adi Shamir:
  A T S^2 = O(2^n) Time/Space Tradeoff for Certain NP-Complete Problems. 328-336
  
• Neil Immerman:
  Length of Predicate Calculus Formulas as a New Complexity Measure. 337-347
  
• Gary L. Peterson, John H. Reif:
  Multiple-Person Alternation. 348-363
  
• Ofer Gabber, Zvi Galil:
  Explicit Constructions of Linear Size Superconcentrators. 364-370
  

Session VI

• Stephen Cole Kleene:
  Origins of Recursive Function Theory. 371-382
  
• Gilles Brassard:
  Relativized Cryptography. 383-391
  
• Theodore P. Baker, Juris Hartmanis:
  Succinctness, Verifiability and Determinism in Representations of Polynomial-Time Languages. 392-396
  
• Leonard M. Adleman, Kenneth L. Manders:
  Reductions that Lie. 397-410
  
• Janos Simon:
  Division Is Good. 411-420
  
• John H. Reif:
  Complexity of the Mover's Problem and Generalizations (Extended Abstract). 421-427
  

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