## Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, Lawrence H. Landweber

*Proceedings of the 14th Annual ACM Symposium on Theory of Computing*

STOC, 1982.

@proceedings{STOC-1982, address = "San Francisco, California, USA", doi = "10.1145/800070", editor = "Harry R. Lewis and Barbara B. Simons and Walter A. Burkhard and Lawrence H. Landweber", isbn = "0-89791-067-2", publisher = "{ACM}", title = "{Proceedings of the 14th Annual ACM Symposium on Theory of Computing}", year = 1982, }

### Contents (45 items)

- STOC-1982-DurisG #nondeterminism
- Two Tapes are Better than One for Nondeterministic Machines (PD, ZG), pp. 1–7.
- STOC-1982-Furer
- The Tight Deterministic Time Hierarchy (MF), pp. 8–16.
- STOC-1982-Pippenger #probability #simulation
- Probabilistic Simulations (NP), pp. 17–26.
- STOC-1982-Vitanyi #multi #realtime #simulation #turing machine
- Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines (PMBV), pp. 27–36.
- STOC-1982-InoueTT #2d #turing machine
- Two-Dimensional Alternating Turing Machines (KI, IT, HT), pp. 37–46.
- STOC-1982-NivatP
- Ensembles Reconnaissables de Mots Biinfinis (MN, DP), pp. 47–59.
- STOC-1982-GurevichH #automaton #game studies
- Trees, Automata, and Games (YG, LH), pp. 60–65.
- STOC-1982-Carter #formal method #testing
- The Theory of Signature Testing for VLSI (JLC), pp. 66–76.
- STOC-1982-BhattL #how
- How to Assemble Tree Machines (SNB, CEL), pp. 77–84.
- STOC-1982-Leighton #layout
- A Layout Strategy for VLSI which Is Provably Good (FTL), pp. 85–98.
- STOC-1982-Kissin #energy
- Measuring Energy Consumption in VLSI Circuits: a Foundation (GK), pp. 99–104.
- STOC-1982-RivestS #how #memory management #reuse
- How to Reuse a “Write-Once” Memory (RLR, AS), pp. 105–113.
- STOC-1982-Willard #maintenance
- Maintaining Dense Sequential Files in a Dynamic Environment (DEW), pp. 114–121.
- STOC-1982-Dietz #maintenance #order
- Maintaining Order in a Linked List (PFD), pp. 122–127.
- STOC-1982-Yao #query #trade-off
- Space-Time Tradeoff for Answering Range Queries (ACCY), pp. 128–136.
- STOC-1982-Vardi #complexity #query #relational
- The Complexity of Relational Query Languages (MYV), pp. 137–146.
- STOC-1982-Immerman #polynomial #query #relational
- Relational Queries Computable in Polynomial Time (NI), pp. 147–152.
- STOC-1982-DeBakkerZ #concurrent #semantics
- Denotational Semantics of Concurrency (JWdB, JIZ), pp. 153–158.
- STOC-1982-SistlaC #complexity #linear #logic
- The Complexity of Propositional Linear Temporal Logics (APS, EMC), pp. 159–168.
- STOC-1982-EmersonH #branch #logic
- Decision Procedures and Expressiveness in the Temporal Logic of Branching Time (EAE, JYH), pp. 169–180.
- STOC-1982-FeldmanH #logic #probability
- A Probabilistic Dynamic Logic (YAF, DH), pp. 181–195.
- STOC-1982-PapadimitriouS #communication #complexity
- Communication Complexity (CHP, MS), pp. 196–200.
- STOC-1982-Reif #symmetry
- Symmetric Complementation (JHR), pp. 201–214.
- STOC-1982-RuzzoST #bound #probability
- Space-Bounded Hierarchies and Probabilistic Computations (WLR, JS, MT), pp. 215–223.
- STOC-1982-Kurtz #on the #random
- On the Random Oracle Hypothesis (SAK), pp. 224–230.
- STOC-1982-CookD #bound #parallel #ram
- Bounds on the Time for Parallel RAM’s to Compute Simple Functions (SAC, CD), pp. 231–233.
- STOC-1982-ManberT #nondeterminism #probability
- Probabilistic, Nondeterministic, and Alternating Decision Trees (UM, MT), pp. 234–244.
- STOC-1982-AsanoH #problem
- Edge-Deletion and Edge-Contraction Problems (TA, TH), pp. 245–254.
- STOC-1982-PapadimitriouY #complexity
- The Complexity of Facets (and Some Facets of Complexity) (CHP, MY), pp. 255–260.
- STOC-1982-Kaltofen #multi #polynomial #reduction
- A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization (EK), pp. 261–266.
- STOC-1982-Kosaraju #decidability #reachability
- Decidability of Reachability in Vector Addition Systems (SRK), pp. 267–281.
- STOC-1982-BoyceDDG
- Finding Extremal Polygons (JEB, DPD, RL(DI, LJG), pp. 282–289.
- STOC-1982-Bach #algorithm #performance
- Fast Algorithms under the Extended Riemann Hypothesis: A Concrete Estimate (EB), pp. 290–295.
- STOC-1982-HongS #network
- Notes on Merging Networks (ZH, RS), pp. 296–302.
- STOC-1982-Bar-YehudaE #approximate #graph #on the
- On Approximating a Vertex Cover for Planar Graphs (RBY, SE), pp. 303–309.
- STOC-1982-BabaiGM #bound #graph #morphism #multi
- Isomorphism of Graphs with Bounded Eigenvalue Multiplicity (LB, DYG, DMM), pp. 310–324.
- STOC-1982-Wigderson #algorithm #approximate #graph
- A New Approximate Graph Coloring Algorithm (AW), pp. 325–329.
- STOC-1982-MehlhornS #distributed
- Las Vegas Is better than Determinism in VLSI and Distributed Computing (KM, EMS), pp. 330–337.
- STOC-1982-BorodinH #modelling #parallel #sorting
- Routing, Merging and Sorting on Parallel Models of Computation (AB, JEH), pp. 338–344.
- STOC-1982-AtallahK #array #graph #problem
- Graph Problems on a Mesh-Connected Processor Array (MJA, SRK), pp. 345–353.
- STOC-1982-Greenberg #communication #complexity #on the
- On the Time Complexity of Broadcast Communication Schemes (AGG), pp. 354–364.
- STOC-1982-GoldwasserM #encryption #game studies #how #probability
- Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information (SG, SM), pp. 365–377.
- STOC-1982-PachlKR #algorithm #bound #distributed #proving
- A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms (JKP, EK, DR), pp. 378–382.
- STOC-1982-DeMilloLM #encryption #protocol
- Cryptographic Protocols (RAD, NAL, MM), pp. 383–400.
- STOC-1982-DolevS #algorithm #multi #polynomial
- Polynomial Algorithms for Multiple Processor Agreement (DD, HRS), pp. 401–407.

5 ×#complexity

5 ×#probability

4 ×#algorithm

4 ×#bound

4 ×#graph

4 ×#multi

3 ×#how

3 ×#logic

3 ×#on the

3 ×#polynomial

5 ×#probability

4 ×#algorithm

4 ×#bound

4 ×#graph

4 ×#multi

3 ×#how

3 ×#logic

3 ×#on the

3 ×#polynomial