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