Alfred V. Aho
Proceedings of the 19th Annual ACM Symposium on Theory of Computing
STOC, 1987.

@proceedings{STOC-1987,
	address       = "1987, New York, USA",
	editor        = "Alfred V. Aho",
	isbn          = "0-89791-221-7",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 19th Annual ACM Symposium on Theory of Computing}",
	year          = 1987,
}

Contents (50 items)

10 ×#algorithm
8 ×#graph
7 ×#complexity
5 ×#problem
5 ×#random
4 ×#parallel
3 ×#on the
2 ×#algebra
2 ×#analysis
2 ×#approximate

STOC-1987-CoppersmithW #matrix #multi

Matrix Multiplication via Arithmetic Progressions (DC, SW), pp. 1–6.

STOC-1987-GoldbergT #approximate #low cost #problem

Solving Minimum-Cost Flow Problems by Successive Approximation (AVG, RET), pp. 7–18.

STOC-1987-Frederickson #approach #graph

A New Approach to All Pairs Shortest Paths in Planar Graphs (GNF), pp. 19–28.

STOC-1987-Vaidya #algorithm #linear #programming

An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations (PMV), pp. 29–38.

STOC-1987-AggarwalGSS #algorithm #diagrams #linear

A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon (AA, LJG, JBS, PWS), pp. 39–45.

STOC-1987-IwanoS #graph #infinity #testing

Testing for Cycles in Infinite Graphs with Periodic Structure (KI, KS), pp. 46–55.

STOC-1987-Clarkson #algorithm #approximate

Approximation Algorithms for Shortest Path Motion Planning (KLC), pp. 56–65.

STOC-1987-ChazelleEG #complexity

The Complexity of Cutting Convex Polytopes (BC, HE, LJG), pp. 66–76.

STOC-1987-Smolensky #algebra #bound #complexity #formal method

Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity (RS), pp. 77–82.

STOC-1987-BeameH #bound #problem

Optimal Bounds for Decision Problems on the CRCW PRAM (PB, JH), pp. 83–93.

STOC-1987-MaassSS #turing machine

Two Tapes Are Better than One for Off-Line Turing Machines (WM, GS, ES), pp. 94–100.

STOC-1987-BarringtonT #finite #monad

Finite Monoids and the Fine Structure of NC¹ (DAMB, DT), pp. 101–109.

STOC-1987-Hemachandra #exponential

The Strong Exponential Hierarchy Collapses (LAH), pp. 110–122.

STOC-1987-Buss #problem

The Boolean Formula Value Problem Is in ALOGTIME (SRB), pp. 123–131.

STOC-1987-AjtaiKS #simulation

Deterministic Simulation in LOGSPACE (MA, JK, ES), pp. 132–140.

STOC-1987-Venkateswaran

Properties that Characterize LOGCFL (HV), pp. 141–150.

STOC-1987-Allender #generative #pseudo

Some Consequences of the Existence of Pseudorandom Generators (EA), pp. 151–159.

STOC-1987-Vazirani #performance #using

Efficiency Considerations in Using Semi-random Sources (UVV), pp. 160–168.

STOC-1987-LichtensteinLS #process #random

Imperfect Random Sources and Discrete Controlled Processes (DL, NL, MES), pp. 169–177.

STOC-1987-Furer #communication #complexity #power of

The Power of Randomness for Communication Complexity (MF), pp. 178–181.

STOC-1987-Goldreich #formal method #simulation #towards

Towards a Theory of Software Protection and Simulation by Oblivious RAMs (OG), pp. 182–194.

STOC-1987-AbadiFK #on the

On Hiding Information from an Oracle (MA, JF, JK), pp. 195–203.

STOC-1987-Fortnow #complexity

The Complexity of Perfect Zero-Knowledge (LF), pp. 204–209.

STOC-1987-FeigeFS #proving

Zero Knowledge Proofs of Identity (UF, AF, AS), pp. 210–217.

STOC-1987-GoldreichMW #game studies #how #protocol #theorem

How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority (OG, SM, AW), pp. 218–229.

STOC-1987-Awerbuch #algorithm #distributed #problem #summary

Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary) (BA), pp. 230–240.

STOC-1987-HastadLR #analysis #multi #protocol

Analysis of Backoff Protocols for Multiple Access Channels (JH, FTL, BR), pp. 241–253.

STOC-1987-MillerT #complexity #parallel

Dynamic Parallel Complexity of Computational Circuits (GLM, SHT), pp. 254–263.

STOC-1987-PelegU #graph

Constructing Disjoint Paths on Expander Graphs (DP, EU), pp. 264–273.

STOC-1987-HastadLN #configuration management #fault

Reconfiguring a Hypercube in the Presence of Faults (JH, FTL, MN), pp. 274–284.

STOC-1987-KearnsLPV #on the

On the Learnability of Boolean Formulae (MJK, ML, LP, LGV), pp. 285–295.

STOC-1987-Natarajan #learning #on the

On Learning Boolean Functions (BKN), pp. 296–304.

STOC-1987-AggarwalACS #memory management

A Model for Hierarchical Memory (AA, BA, AKC, MS), pp. 305–314.

STOC-1987-GoldbergPS #graph #parallel #symmetry

Parallel Symmetry-Breaking in Sparse Graphs (AVG, SAP, GES), pp. 315–324.

STOC-1987-AggarwalA #algorithm #random

A Random NC Algorithm for Depth First Search (AA, RJA), pp. 325–334.

STOC-1987-MillerR #algorithm #graph #parallel

A New Graph Triconnectivity Algorithm and Its Parallelization (GLM, VR), pp. 335–344.

STOC-1987-MulmuleyVV #matrix

Matching Is as Easy as Matrix Inversion (KM, UVV, VVV), pp. 345–354.

STOC-1987-NaorNS #algorithm #graph #parallel #performance

Fast Parallel Algorithms for Chordal Graphs (JN, MN, AAS), pp. 355–364.

STOC-1987-DietzS #algorithm #maintenance #order

Two Algorithms for Maintaining Order in a List (PFD, DDS), pp. 365–372.

STOC-1987-BorodinLS #algorithm #online

An Optimal Online Algorithm for Metrical Task Systems (AB, NL, MES), pp. 373–382.

STOC-1987-Munro

Searching a Two Key Table Under a Single Key (JIM), pp. 383–387.

STOC-1987-HeathI #graph

The Pagenumber of Genus g Graphs is O(g) (LSH, SI), pp. 388–397.

STOC-1987-Ronyai #algebra

Simple Algebras Are Difficult (LR), pp. 398–408.

STOC-1987-BabaiLS #permutation

Permutation Groups in NC (LB, EML, ÁS), pp. 409–420.

STOC-1987-ShelahS #graph #random

Threshold Spectra for Random Graphs (SS, JS), pp. 421–424.

STOC-1987-KolaitisV #higher-order #problem

The Decision Problem for the Probabilities of Higher-Order Properties (PGK, MYV), pp. 425–435.

STOC-1987-BilardiP #complexity #network

Size-Time Complexity of Boolean Networks for Prefix Computations (GB, FPP), pp. 436–442.

STOC-1987-Kaltofen #complexity

Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials (EK), pp. 443–452.

STOC-1987-Bach #algorithm #analysis #random

Realistic Analysis of Some Randomized Algorithms (EB), pp. 453–461.

STOC-1987-AdlemanH #polynomial #random

Recognizing Primes in Random Polynomial Time (LMA, MDAH), pp. 462–469.