14. STOC 1982
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. ACM 1982
- Pavol Duris, Zvi Galil:
Two Tapes are Better than One for Nondeterministic Machines.
1-7 BibTeX
- Martin Fürer:
The Tight Deterministic Time Hierarchy.
8-16 BibTeX
- Nicholas Pippenger:
Probabilistic Simulations (Preliminary Version).
17-26 BibTeX
- Paul M. B. Vitányi:
Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines.
27-36 BibTeX
- Katsushi Inoue, Itsuo Takanami, Hiroshi Taniguchi:
Two-Dimensional Alternating Turing Machines.
37-46 BibTeX
- Maurice Nivat, Dominique Perrin:
Ensembles Reconnaissables de Mots Biinfinis.
47-59 BibTeX
- Yuri Gurevich, Leo Harrington:
Trees, Automata, and Games.
60-65 BibTeX
- J. Lawrence Carter:
The Theory of Signature Testing for VLSI.
66-76 BibTeX
- Sandeep N. Bhatt, Charles E. Leiserson:
How to Assemble Tree Machines (Extended Abstract).
77-84 BibTeX
- Frank Thomson Leighton:
A Layout Strategy for VLSI which Is Provably Good (Extended Abstract).
85-98 BibTeX
- Gloria Kissin:
Measuring Energy Consumption in VLSI Circuits: a Foundation.
99-104 BibTeX
- Ronald L. Rivest, Adi Shamir:
How to Reuse a ``Write-Once'' Memory (Preliminary Version).
105-113 BibTeX
- Dan E. Willard:
Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract).
114-121 BibTeX
- Paul F. Dietz:
Maintaining Order in a Linked List.
122-127 BibTeX
- Andrew Chi-Chih Yao:
Space-Time Tradeoff for Answering Range Queries (Extended Abstract).
128-136 BibTeX
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
137-146 BibTeX
- Neil Immerman:
Relational Queries Computable in Polynomial Time (Extended Abstract).
147-152 BibTeX
- J. W. de Bakker, Jeffery I. Zucker:
Denotational Semantics of Concurrency.
153-158 BibTeX
- A. Prasad Sistla, Edmund M. Clarke:
The Complexity of Propositional Linear Temporal Logics.
159-168 BibTeX
- E. Allen Emerson, Joseph Y. Halpern:
Decision Procedures and Expressiveness in the Temporal Logic of Branching Time.
169-180 BibTeX
- Yishai A. Feldman, David Harel:
A Probabilistic Dynamic Logic.
181-195 BibTeX
- Christos H. Papadimitriou, Michael Sipser:
Communication Complexity.
196-200 BibTeX
- John H. Reif:
Symmetric Complementation.
201-214 BibTeX
- Walter L. Ruzzo, Janos Simon, Martin Tompa:
Space-Bounded Hierarchies and Probabilistic Computations.
215-223 BibTeX
- Stuart A. Kurtz:
On the Random Oracle Hypothesis.
224-230 BibTeX
- Stephen Cook, Cynthia Dwork:
Bounds on the Time for Parallel RAM's to Compute Simple Functions.
231-233 BibTeX
- Udi Manber, Martin Tompa:
Probabilistic, Nondeterministic, and Alternating Decision Trees.
234-244 BibTeX
- Takao Asano, Tomio Hirata:
Edge-Deletion and Edge-Contraction Problems.
245-254 BibTeX
- Christos H. Papadimitriou, Mihalis Yannakakis:
The Complexity of Facets (and Some Facets of Complexity).
255-260 BibTeX
- Erich Kaltofen:
A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization.
261-266 BibTeX
- S. Rao Kosaraju:
Decidability of Reachability in Vector Addition Systems (Preliminary Version).
267-281 BibTeX
- James E. Boyce, David P. Dobkin, Robert L. (Scot) Drysdale III, Leonidas J. Guibas:
Finding Extremal Polygons.
282-289 BibTeX
- Eric Bach:
Fast Algorithms under the Extended Riemann Hypothesis: A Concrete Estimate.
290-295 BibTeX
- Zhu Hong, Robert Sedgewick:
Notes on Merging Networks (Preliminary Version).
296-302 BibTeX
- Reuven Bar-Yehuda, Shimon Even:
On Approximating a Vertex Cover for Planar Graphs.
303-309 BibTeX
- László Babai, D. Yu. Grigoryev, David M. Mount:
Isomorphism of Graphs with Bounded Eigenvalue Multiplicity.
310-324 BibTeX
- Avi Wigderson:
A New Approximate Graph Coloring Algorithm.
325-329 BibTeX
- Kurt Mehlhorn, Erik Meineche Schmidt:
Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract).
330-337 BibTeX
- Allan Borodin, John E. Hopcroft:
Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract).
338-344 BibTeX
- Mikhail J. Atallah, S. Rao Kosaraju:
Graph Problems on a Mesh-Connected Processor Array (Preliminary Version).
345-353 BibTeX
- Albert G. Greenberg:
On the Time Complexity of Broadcast Communication Schemes (Preliminary Version).
354-364 BibTeX
- Shafi Goldwasser, Silvio Micali:
Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information.
365-377 BibTeX
- Jan K. Pachl, Ephraim Korach, Doron Rotem:
A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms.
378-382 BibTeX
- Richard A. DeMillo, Nancy A. Lynch, Michael Merritt:
Cryptographic Protocols.
383-400 BibTeX
- Danny Dolev, H. Raymond Strong:
Polynomial Algorithms for Multiple Processor Agreement.
401-407 BibTeX
Copyright © Sat May 16 23:43:10 2009
by Michael Ley (ley@uni-trier.de)