Proceedings of the 21st Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

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

TCS
DBLP
Scholar
Full names Links ISxN
@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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.