20. FOCS 1979:
San Juan,
Puerto Rico
20th Annual Symposium on Foundations of Computer Science,
San Juan, Puerto Rico, 29-31 October 1979. IEEE Computer Society
- 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
- 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
- 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
- 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
- Wolfgang J. Paul, Rüdiger Reischuk:
On Time versus Space II.
298-306
- 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
- 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
Copyright © Tue Nov 17 00:20:23 2009
by Michael Ley (ley@uni-trier.de)