David S. Johnson
Proceedings of the 21st Annual ACM Symposium on Theory of Computing
STOC, 1989.

@proceedings{STOC-1989,
	address       = "Washigton, USA",
	editor        = "David S. Johnson",
	isbn          = "0-89791-307-8",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 21st Annual ACM Symposium on Theory of Computing}",
	year          = 1989,
}

Contents (56 items)

9 ×#on the
7 ×#algorithm
5 ×#graph
5 ×#polynomial
4 ×#approximate
4 ×#automaton
4 ×#performance
4 ×#random
3 ×#complexity
3 ×#problem

STOC-1989-BabaiNS #multi #protocol #pseudo #sequence

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (LB, NN, MS), pp. 1–11.

STOC-1989-ImpagliazzoLL #generative #pseudo

Pseudo-random Generation from one-way functions (RI, LAL, ML), pp. 12–24.

STOC-1989-GoldreichL

A Hard-Core Predicate for all One-Way Functions (OG, LAL), pp. 25–32.

STOC-1989-NaorY #encryption

Universal One-Way Hash Functions and their Cryptographic Applications (MN, MY), pp. 33–43.

STOC-1989-ImpagliazzoR #permutation

Limits on the Provable Consequences of One-Way Permutations (RI, SR), pp. 44–61.

STOC-1989-ChorK #privacy

A Zero-One Law for Boolean Privacy (BC, EK), pp. 62–72.

STOC-1989-RabinB #multi #protocol

Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (TR, MBO), pp. 73–85.

STOC-1989-BlumK #design #source code

Designing Programs That Check Their Work (MB, SK), pp. 86–97.

STOC-1989-Vallee #integer #performance #polynomial

Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues (BV), pp. 98–106.

STOC-1989-CookU #functional

Functional Interpretations of Feasibly Constructive Arithmetic (SAC, AU), pp. 107–112.

STOC-1989-AfratiC #query #recursion #strict

Expressiveness of Restricted Recursive Queries (FNA, SSC), pp. 113–126.

STOC-1989-SafraV #automaton #logic #on the

On ω-Automata and Temporal Logic (SS, MYV), pp. 127–137.

STOC-1989-Ierardi #algebra #formal method #quantifier

Quantifier Elimination in the Theory of an Algebraically-closed Field (DI), pp. 138–147.

STOC-1989-FortnowS #linear #probability

Probabilistic Computation and Linear Time (LF, MS), pp. 148–156.

STOC-1989-KurtzMR #morphism #random

The Isomorphism Conjecture Fails Relative to a Random Oracle (SAK, SRM, JSR), pp. 157–166.

STOC-1989-Razborov #approximate #on the

On the Method of Approximations (AAR), pp. 167–176.

STOC-1989-Bshouty #on the

On the Extended Direct Sum Conjecture (NHB), pp. 177–185.

STOC-1989-Yao

Circuits and Local Computation (ACCY), pp. 186–196.

STOC-1989-Beame #trade-off

A General Sequential Time-Space Tradeoff for Finding Unique Elements (PB), pp. 197–203.

STOC-1989-Ben-DavidCGL #complexity #formal method #on the

On the Theory of Average Case Complexity (SBD, BC, OG, ML), pp. 204–216.

STOC-1989-LamTT #communication #trade-off

Tradeoffs Between Communication and Space (TWL, PT, MT), pp. 217–226.

STOC-1989-KochLMRR #network

Work-Preserving Emulations of Fixed-Connection Networks (RRK, FTL, BMM, SR, ALR), pp. 227–240.

STOC-1989-Upfal

An O(log N) Deterministic Packet Routing Scheme (EU), pp. 241–250.

STOC-1989-HastadLN #performance #using

Fast Computation Using Faulty Hypercubes (JH, FTL, MN), pp. 251–263.

STOC-1989-ReifT #integer

Optimal Size Integer Division Circuits (JHR, SRT), pp. 264–273.

STOC-1989-AlonBLP #communication #complexity #on the

On the Complexity of Radio Communication (NA, ABN, NL, DP), pp. 274–285.

STOC-1989-KaoS #order

Local Reorientation, Global Order, and Planar Topology (MYK, GES), pp. 286–296.

STOC-1989-AggarwalAK #graph #parallel

Parallel Depth-First Search in General Directed Graphs (AA, RJA, MYK), pp. 297–308.

STOC-1989-BerkmanBGSV #problem

Highly Parallelizable Problems (OB, DB, ZG, BS, UV), pp. 309–319.

STOC-1989-Boppana #parallel

Optimal Separations Between Concurrent-Write Parallel Machines (RBB), pp. 320–326.

STOC-1989-Nisan

CREW PRAMs and Decision Trees (NN), pp. 327–335.

STOC-1989-FiatN

Implicit O(1) Probe Search (AF, MN), pp. 336–344.

STOC-1989-FredmanS #complexity #data type

The Cell Probe Complexity of Dynamic Data Structures (MLF, MES), pp. 345–354.

STOC-1989-SchmidtS #aspect-oriented #on the #performance

On Aspects of Universality and Performance for Closed Hashing (JPS, AS), pp. 355–366.

STOC-1989-Kenyon-MathieuK #partial order #verification

Verifying Partial Orders (CKM, VK), pp. 367–374.

STOC-1989-DyerFK #algorithm #approximate #polynomial #random

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies (MED, AMF, RK), pp. 375–381.

STOC-1989-ChazelleEGS #algorithm #combinator

Lines in Space-Combinatorics, Algorithms and Applications (BC, HE, LJG, MS), pp. 382–393.

STOC-1989-ReifS #geometry #named #random

Polling: A New Randomized Sampling Technique for Computational Geometry (JHR, SS), pp. 394–404.

STOC-1989-GoodmanPS #coordination #exponential #order #representation

Coordinate Representation of Order Types Requires Exponential Storage (JEG, RP, BS), pp. 405–410.

STOC-1989-RivestS #automaton #finite #sequence #using

Inference of Finite Automata Using Homing Sequences (RLR, RES), pp. 411–420.

STOC-1989-PittW #approximate #automaton #consistency #polynomial #problem

The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial (LP, MKW), pp. 421–432.

STOC-1989-KearnsV #automaton #encryption #finite #learning

Cryptographic Limitations on Learning Boolean Formulae and Finite Automata (MJK, LGV), pp. 433–444.

STOC-1989-Birget #proving

Proof of a Conjecture of R. Kannan (JCB), pp. 445–453.

STOC-1989-DolevS #bound #concurrent

Bounded Concurrent Time-Stamp Systems Are Constructible (DD, NS), pp. 454–466.

STOC-1989-GrahamY #on the

On the Improbability of Reaching Byzantine Agreements (RLG, ACCY), pp. 467–478.

STOC-1989-AwerbuchBLP #adaptation #data type #distributed

Compact Distributed Data Structures for Adaptive Routing (BA, ABN, NL, DP), pp. 479–489.

STOC-1989-Awerbuch #algorithm #distributed

Distributed Shortest Paths Algorithms (BA), pp. 490–500.

STOC-1989-FellowsL #algorithm #on the #performance #polynomial

On Search, Decision and the Efficiency of Polynomial-Time Algorithms (MRF, MAL), pp. 501–512.

STOC-1989-Feder #approach #fixpoint #network

A New Fixed Point Approach for Stable Networks and Stable Marriages (TF), pp. 513–522.

STOC-1989-CohenM #algorithm #detection #graph #polynomial

Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (EC, NM), pp. 523–534.

STOC-1989-Blum #algorithm #approximate

An O(n⁰⋅⁴)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring) (AB), pp. 535–542.

STOC-1989-BroderKRU

Trading Space for Time in Undirected s-t Connectivity (AZB, ARK, PR, EU), pp. 543–549.

STOC-1989-Motwani #algorithm #analysis #graph #problem

Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems (RM), pp. 550–561.

STOC-1989-BorodinRT #bound #sequence #traversal

Lower Bounds on the Length of Universal Traversal Sequences (AB, WLR, MT), pp. 562–573.

STOC-1989-ChandraRRST #graph

The Electrical Resistance of a Graph Captures its Commute and Cover Times (AKC, PR, WLR, RS, PT), pp. 574–586.

STOC-1989-FriedmanKS #graph #on the #random

On the Second Eigenvalue in Random Regular Graphs (JF, JK, ES), pp. 587–598.