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)

5 ×#complexity
5 ×#probability
4 ×#algorithm
4 ×#bound
4 ×#graph
4 ×#multi
3 ×#how
3 ×#logic
3 ×#on the
3 ×#polynomial

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.