## 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)

- 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.

10 ×#algorithm

8 ×#graph

7 ×#complexity

5 ×#problem

5 ×#random

4 ×#parallel

3 ×#on the

2 ×#algebra

2 ×#analysis

2 ×#approximate

8 ×#graph

7 ×#complexity

5 ×#problem

5 ×#random

4 ×#parallel

3 ×#on the

2 ×#algebra

2 ×#analysis

2 ×#approximate