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