22. FOCS 1981: Nashville, Tennessee, USA
22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28-30 October 1981. IEEE Computer Society 1981
Session 1a
- 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
- Zvi M. Kedem, Alessandro Zorat: On Relations Between Input and Communication/Computation in VLSI (Preliminary Report). 37-44
Session 1b
- 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
Session 2
- Don Coppersmith, Shmuel Winograd: On the Asymptotic Complexity of Matrix Multiplication (Extended Summary). 82-90
- 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
- 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
Session 3a
- William C. Rounds, Stephen D. Brookes: Possible Futures, Acceptances, Refusals, and Communicating Processes. 140-149
- Danny Dolev: Unanimity in an Unknown and Unreliable Environment. 159-168
- James E. Burns: Symmetry in Systems of Asynchronous Processes. 169-174
Session 3b
- 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
Session 4
- 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
- Ravi Kannan: Towards Separating Nondeterministic Time from Deterministic Time. 235-243
- 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
Session 5
- 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
- Ravi Kannan: A Circuit-Size Lower Bound. 304-309
- 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
Session 6
- 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
- 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
Late Paper
- Vaughan R. Pratt: A Decidable mu-Calculus: Preliminary Report. 421-427
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team