David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas
Proceedings of the 15th Annual ACM Symposium on Theory of Computing
STOC, 1983.

@proceedings{STOC-1983,
	address       = "Boston, Massachusetts, USA",
	editor        = "David S. Johnson and Ronald Fagin and Michael L. Fredman and David Harel and Richard M. Karp and Nancy A. Lynch and Christos H. Papadimitriou and Ronald L. Rivest and Walter L. Ruzzo and Joel I. Seiferas",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 15th Annual ACM Symposium on Theory of Computing}",
	year          = 1983,
}

Contents (54 items)

7 ×#algorithm
7 ×#bound
5 ×#complexity
5 ×#on the
5 ×#problem
4 ×#polynomial
4 ×#probability
4 ×#set
3 ×#how
3 ×#linear

STOC-1983-AjtaiKS #network #sorting

An O(n log n) Sorting Network (MA, JK, ES), pp. 1–9.

STOC-1983-ReifV #linear #network

A Logarithmic Time Sort for Linear Size Networks (JHR, LGV), pp. 10–16.

STOC-1983-Gathen #algebra #algorithm #parallel #problem

Parallel algorithms for algebraic problems (JvzG), pp. 17–23.

STOC-1983-Stout

Topological Matching (QFS), pp. 24–31.

STOC-1983-Gacs #automaton #reliability

Reliable Computation with Cellular Automata (PG), pp. 32–41.

STOC-1983-DolevDPW

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (DD, CD, NP, AW), pp. 42–51.

STOC-1983-ChandraFL83a #bound

Unbounded Fan-in Circuits and Associative Functions (AKC, SF, RJL), pp. 52–60.

STOC-1983-Sipser #complexity #set

Borel Sets and Circuit Complexity (MS), pp. 61–69.

STOC-1983-Heide #algorithm #linear #polynomial #problem

A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem (FMadH), pp. 70–79.

STOC-1983-Ben-Or #algebra #bound

Lower Bounds for Algebraic Computation Trees (MBO), pp. 80–86.

STOC-1983-BorodinDFP #bound #branch #source code

Bounds for Width Two Branching Programs (AB, DD, FEF, WJP), pp. 87–93.

STOC-1983-ChandraFL83b #multi #protocol

Multi-Party Protocols (AKC, MLF, RJL), pp. 94–99.

STOC-1983-Fich #bound #parallel

New Bounds for Parallel Prefix Circuits (FEF), pp. 100–109.

STOC-1983-Valiant #bound #exponential #strict

Exponential Lower Bounds for Restricted Monotone Circuits (LGV), pp. 110–117.

STOC-1983-Stockmeyer #approximate #complexity

The Complexity of Approximate Counting (LJS), pp. 118–126.

STOC-1983-DurisGPR #bound

Two Nonlinear Lower Bounds (PD, ZG, WJP, RR), pp. 127–132.

STOC-1983-AhoUY #on the

On Notions of Information Transfer in VLSI Circuits (AVA, JDU, MY), pp. 133–139.

STOC-1983-LandauM #polynomial

Solvability by Radicals is in Polynomial Time (SL, GLM), pp. 140–151.

STOC-1983-DriscollF #on the #permutation

On the Diameter of Permutation Groups (JRD, MLF), pp. 152–160.

STOC-1983-FurerSS #bound #graph #normalisation

Normal Forms for Trivalent Graphs and Graphs of Bounded Valence (MF, WS, ES), pp. 161–170.

STOC-1983-BabaiL #canonical #graph

Canonical Labeling of Graphs (LB, EML), pp. 171–183.

STOC-1983-Bach #how #integer #random

How to Generate Random Integers with Known Factorization (EB), pp. 184–188.

STOC-1983-Lenstra #finite #multi

Factoring Multivariate Polynomials over Finite Fields (AKL), pp. 189–192.

STOC-1983-Kannan #algorithm #integer #problem #programming

Improved Algorithms for Integer Programming and Related Lattice Problems (RK), pp. 193–206.

STOC-1983-ODunlaingSY #approach #named

Retraction: A New Approach to Motion-Planning (CÓ, MS, CKY), pp. 207–220.

STOC-1983-GuibasS #diagrams

Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams (LJG, JS), pp. 221–234.

STOC-1983-SleatorT #self

Self-Adjusting Binary Trees (DDS, RET), pp. 235–245.

STOC-1983-GabowT #algorithm #linear #set

A Linear-Time Algorithm for a Special Case of Disjoint Set Union (HNG, RET), pp. 246–251.

STOC-1983-Frederickson #data type #online

Data Structures for On-Line Updating of Minimum Spanning Trees (GNF), pp. 252–257.

STOC-1983-Yao

A 3-Space Partition and Its Applications (FFY), pp. 258–263.

STOC-1983-KanellakisCV #dependence #polynomial #problem

Unary Inclusion Dependencies have Polynomial Time Inference Problems (PCK, SSC, MYV), pp. 264–277.

STOC-1983-Pnueli #algorithm #on the #probability

On the Extremely Fair Treatment of Probabilistic Algorithms (AP), pp. 278–290.

STOC-1983-Kozen #probability

A Probabilistic PDL (DK), pp. 291–297.

STOC-1983-Feldman #decidability #logic #probability

A Decidable Propositional Probabilistic Dynamic Logic (YAF), pp. 298–309.

STOC-1983-HalpernR #logic

A Logic to Reason about Likelihood (JYH, MOR), pp. 310–319.

STOC-1983-Olderog #hoare #logic #source code

A Characterization of Hoare’s Logic for Programs with Pascal-like Procedures (ERO), pp. 320–329.

STOC-1983-Sipser83a #approach #complexity

A Complexity Theoretic Approach to Randomness (MS), pp. 330–335.

STOC-1983-DymondT #parallel

Speedups of Deterministic Machines by Synchronous Parallel Machines (PWD, MT), pp. 336–343.

STOC-1983-Kannan83a #nondeterminism #power of

Alternation and the Power of Nondeterminism (RK), pp. 344–346.

STOC-1983-Immerman #complexity

Languages Which Capture Complexity Classes (NI), pp. 347–354.

STOC-1983-Myers #random

The Random Access Hierarchy (DM), pp. 355–364.

STOC-1983-Engelfriet #automaton #complexity

Iterated Pushdown Automata and Complexity Classes (JE), pp. 365–373.

STOC-1983-Iwama #communication #multi #string

Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication (KI), pp. 374–381.

STOC-1983-HartmanisSI #set

Sparse Sets in NP-P: EXPTIME versus NEXPTIME (JH, VS, NI), pp. 382–391.

STOC-1983-Young #polynomial #set

Some Structural Properties of Polynomial Reducibilities and Sets in NP (PY), pp. 392–401.

STOC-1983-Adleman #on the

On Breaking Generalized Knapsack Public Key Cryptosystems (LMA), pp. 402–412.

STOC-1983-LongW #how #question

How Discreet is the Discrete Log? (DLL, AW), pp. 413–420.

STOC-1983-Ben-OrCS #encryption #on the #security

On the Cryptographic Security of Single RSA Bits (MBO, BC, AS), pp. 421–430.

STOC-1983-GoldwasserMY

Strong Signature Schemes (SG, SM, ACCY), pp. 431–439.

STOC-1983-Blum #how

How to Exchange (Secret) Keys (MB), pp. 440–447.

STOC-1983-Gabow #network #performance #problem #reduction

An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems (HNG), pp. 448–456.

STOC-1983-Spinrad #transitive

Transitive Orientation in O(n²) Time (JPS), pp. 457–466.

STOC-1983-Turner #algorithm #analysis #probability

Probabilistic Analysis of Bandwidth Minimization Algorithms (JST), pp. 467–476.

STOC-1983-BakerBL #algorithm #approximate

An Approximation Algorithm for Manhattan Routing (BSB, SNB, FTL), pp. 477–486.