22. FOCS 1981:
Nashville,
Tennessee
22nd Annual Symposium on Foundations of Computer Science,
Nashville, Tennessee, 28-30 October 1981. IEEE Computer Society
- Frank Thomson Leighton:
New Lower Bound Techniques for VLSI.
1-12
- Richard J. Lipton, Jacobo Valdes:
Census Functions: an Approach to VLSI Upper Bounds (Preliminary Version).
13-22
- Charles E. Leiserson, James B. Saxe:
Optimizing Synchronous Systems.
23-36
- Zvi M. Kedem, Alessandro Zorat:
On Relations Between Input and Communication/Computation in VLSI (Preliminary Report).
37-44
- Eitan M. Gurari, Oscar H. Ibarra:
Two-Way Counter Machines and Diophantine Equations.
45-52
- Pavol Duris, Zvi Galil:
A Time-Space Tradeoff for Language Recognition.
53-57
- Michael C. Loui:
Simulations among Multidimensional Turing Machines (Preliminary Version).
58-67
- Wolfgang J. Paul:
On Heads Versus Tapes.
68-73
- Richard Edwin Stearns, Harry B. Hunt III:
On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Grammars, and Automata.
74-81
- Don Coppersmith, Shmuel Winograd:
On the Asymptotic Complexity of Matrix Multiplication (Extended Summary).
82-90
- Ephraim Feig, Shmuel Winograd:
On the Direct Sum Conjecture (Extended Summary).
91-94
- Joseph JáJá:
Computation of Algebraic Functions with Root Extractions.
95-100
- Norbert Blum:
An Omega(n^4/3) Lower Bound on the Monotone Network Complexity of n-th Degree Convolution.
101-108
- Maria M. Klawe:
Non-Existence of One-Dimensional Expanding Graphs.
109-114
- Mark J. Post:
A Minimum Spanning Ellipse Algorithm.
115-122
- Z. Aviad, E. Shamir:
A Direct Dynamic Solution to Range Search and Related Problems for Product Regions.
123-126
- Jeffrey Scott Vitter:
Deletion Algorithms for Hashing that Preserve Randomness (detailed abstract).
127-132
- Greg N. Frederickson:
Implicit Data Structures for the Weighted Dictionary Problem (preliminary version).
133-139
- William C. Rounds, Stephen D. Brookes:
Possible Futures, Acceptances, Refusals, and Communicating Processes.
140-149
- Alon Itai, Michael Rodeh:
Symmetry Breaking in Distributive Networks.
150-158
- Danny Dolev:
Unanimity in an Unknown and Unreliable Environment.
159-168
- James E. Burns:
Symmetry in Systems of Asynchronous Processes.
169-174
- Ravi Sethi:
A model of concurrent database transactions (summary).
175-184
- Paris C. Kanellakis, Christos H. Papadimitriou:
The Complexity of Distributed Concurrency Control.
185-197
- Moshe Y. Vardi:
Global Decision Problems for Relational Databases.
198-202
- David S. Johnson, Anthony C. Klug:
Optimizing Conjunctive Queries When Attribute Domains Are not Disjoint (Extended Abstract).
203-211
- Rüdiger Reischuk:
A Fast Probabilistic Parallel Sorting Algorithm.
212-219
- Udi Manber, Martin Tompa:
The Effect of Number of Hamiltonian Paths on the Complexity of a Vertex-Coloring Problem.
220-227
- Rutger Verbeek:
Time-Space Trade-Offs for General Recursion.
228-234
- Sven Skyum, Leslie G. Valiant:
A Complexity Theory Based on Boolean Algebra.
244-253
- Ronald V. Book, Christopher B. Wilson, Mei-rui Xu:
Relativizing Time and Space (Preliminary Report).
254-259
- Merrick L. Furst, James B. Saxe, Michael Sipser:
Parity, Circuits, and the Polynomial-Time Hierarchy.
260-270
- Stephen R. Mahaney:
On the Number of P-Isomorphism Classes of NP-Complete Sets.
271-278
- Richard Statman:
Number Theoretic Functions Computable by Polymorphic Programs (Extended Abstract).
279-282
- Carl H. Smith:
The Power of Parallelism for Automatic Program Synthesis.
283-295
- Péter Gács:
On the Relation between Descriptional Complexity and Algorithmic Probability.
296-303
- David Harel, Amir Pnueli, Jonathan Stavi:
Propositional Dynamic Logic of Context-Free Programs.
310-321
- Joseph Y. Halpern, John H. Reif:
The Propositional Dynamic Logic of Deterministic, Well-Structured Programs (Extended Abstract).
322-334
- Jerzy Tiuryn:
Unbounded Program Memory Adds to the Expressive Power of First-Order Dynamic Logic (Extended Abstract).
335-339
- Pierre Wolper:
Temporal Logic Can Be More Expressive.
340-348
- Danny Dolev, Andrew Chi-Chih Yao:
On the Security of Public Key Protocols (Extended Abstract).
350-357
- Christos H. Papadimitriou, Mihalis Yannakakis:
Worst-Case Ratios for Planar Graphs and the Method of Induction on Faces (Extended Abstract).
358-363
- Richard M. Karp, Michael Sipser:
Maximum Matchings in Sparse Random Graphs.
364-375
- Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, David S. Johnson, Christos H. Papadimitriou:
The Complexity of Searching a Graph (Preliminary Version).
376-385
- Philippe Flajolet, Jean-Marc Steyaert:
A Complexity Calculus for Classes of Recursive Search Programs over Tree Structures.
386-393
- Michael Ben-Or:
Probabilistic Algorithms in Finite Fields.
394-398
- Nimrod Megiddo:
Applying Parallel Computation Algorithms in the Design of Serial Algorithms.
399-408
- Leonard M. Adleman, Andrew M. Odlyzko:
Irreducibility Testing and Factorization of Polynomials (Extended Abstract).
409-418
- Vaughan R. Pratt:
A Decidable mu-Calculus: Preliminary Report.
421-427
Copyright © Tue Dec 1 16:15:03 2009
by Michael Ley (ley@uni-trier.de)
