22. FOCS 1981: Nashville, Tennessee, USA

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
  
• 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
  

Session 1b

• 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
  

Session 2

• 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
  

Session 3a

• 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
  

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
  
• 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
  

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
  
• 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
  

Late Paper

• Vaughan R. Pratt:
  A Decidable mu-Calculus: Preliminary Report. 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