default search action
22nd 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 - 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 F. 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, Eli 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-23 19:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: