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

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

9 ×#on the

7 ×#algorithm

5 ×#graph

5 ×#polynomial

4 ×#approximate

4 ×#automaton

4 ×#performance

4 ×#random

3 ×#complexity

3 ×#problem

7 ×#algorithm

5 ×#graph

5 ×#polynomial

4 ×#approximate

4 ×#automaton

4 ×#performance

4 ×#random

3 ×#complexity

3 ×#problem