21. STOC 1989: Seattle, Washigton, USA
David S. Johnson (Ed.):
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA.
ACM 1989, ISBN 0-89791-307-8
- László Babai, Noam Nisan, Mario Szegedy:
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract).
1-11

- Russell Impagliazzo, Leonid A. Levin, Michael Luby:
Pseudo-random Generation from one-way functions (Extended Abstracts).
12-24

- Oded Goldreich, Leonid A. Levin:
A Hard-Core Predicate for all One-Way Functions.
25-32

- Moni Naor, Moti Yung:
Universal One-Way Hash Functions and their Cryptographic Applications.
33-43

- Russell Impagliazzo, Steven Rudich:
Limits on the Provable Consequences of One-Way Permutations.
44-61

- Benny Chor, Eyal Kushilevitz:
A Zero-One Law for Boolean Privacy (extended abstract).
62-72

- Tal Rabin, Michael Ben-Or:
Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract).
73-85

- Manuel Blum, Sampath Kannan:
Designing Programs That Check Their Work.
86-97

- Brigitte Vallée:
Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues.
98-106

- Stephen A. Cook, Alasdair Urquhart:
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract).
107-112

- Foto N. Afrati, Stavros S. Cosmadakis:
Expressiveness of Restricted Recursive Queries (Extended Abstract).
113-126

- Shmuel Safra, Moshe Y. Vardi:
On omega-Automata and Temporal Logic (Preliminary Report).
127-137

- Doug Ierardi:
Quantifier Elimination in the Theory of an Algebraically-closed Field.
138-147

- Lance Fortnow, Michael Sipser:
Probabilistic Computation and Linear Time.
148-156

- Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer:
The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract).
157-166

- Alexander A. Razborov:
On the Method of Approximations.
167-176

- Nader H. Bshouty:
On the Extended Direct Sum Conjecture.
177-185

- Andrew Chi-Chih Yao:
Circuits and Local Computation.
186-196

- Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements.
197-203

- Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:
On the Theory of Average Case Complexity.
204-216

- Tak Wah Lam, Prasoon Tiwari, Martin Tompa:
Tradeoffs Between Communication and Space.
217-226

- Richard R. Koch, Frank Thomson Leighton, Bruce M. Maggs, Satish Rao, Arnold L. Rosenberg:
Work-Preserving Emulations of Fixed-Connection Networks (Extended Abstract).
227-240

- Eli Upfal:
An O(log N) Deterministic Packet Routing Scheme (Preliminary Version).
241-250

- Johan Håstad, Frank Thomson Leighton, Mark Newman:
Fast Computation Using Faulty Hypercubes (Extended Abstract).
251-263

- John H. Reif, Stephen R. Tate:
Optimal Size Integer Division Circuits.
264-273

- Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
On the Complexity of Radio Communication (Extended Abstract).
274-285

- Ming-Yang Kao, Gregory E. Shannon:
Local Reorientation, Global Order, and Planar Topology (Preliminary Version).
286-296

- Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao:
Parallel Depth-First Search in General Directed Graphs (Preliminary Version).
297-308

- Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin:
Highly Parallelizable Problems (Extended Abstract).
309-319

- Ravi B. Boppana:
Optimal Separations Between Concurrent-Write Parallel Machines.
320-326

- Noam Nisan:
CREW PRAMs and Decision Trees.
327-335

- Amos Fiat, Moni Naor:
Implicit O(1) Probe Search.
336-344

- Michael L. Fredman, Michael E. Saks:
The Cell Probe Complexity of Dynamic Data Structures.
345-354

- Jeanette P. Schmidt, Alan Siegel:
On Aspects of Universality and Performance for Closed Hashing (Extended Abstract).
355-366

- Claire Kenyon-Mathieu, Valerie King:
Verifying Partial Orders.
367-374

- Martin E. Dyer, Alan M. Frieze, Ravi Kannan:
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
375-381

- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir:
Lines in Space-Combinatorics, Algorithms and Applications.
382-393

- John H. Reif, Sandeep Sen:
Polling: A New Randomized Sampling Technique for Computational Geometry.
394-404

- Jacob E. Goodman, Richard Pollack, Bernd Sturmfels:
Coordinate Representation of Order Types Requires Exponential Storage.
405-410

- Ronald L. Rivest, Robert E. Schapire:
Inference of Finite Automata Using Homing Sequences (Extended Abstract).
411-420

- Leonard Pitt, Manfred K. Warmuth:
The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial.
421-432

- Michael J. Kearns, Leslie G. Valiant:
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
433-444

- Jean-Camille Birget:
Proof of a Conjecture of R. Kannan.
445-453

- Danny Dolev, Nir Shavit:
Bounded Concurrent Time-Stamp Systems Are Constructible.
454-466

- Ronald L. Graham, Andrew Chi-Chih Yao:
On the Improbability of Reaching Byzantine Agreements (Preliminary Version).
467-478

- Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg:
Compact Distributed Data Structures for Adaptive Routing (Extended Abstract).
479-489

- Baruch Awerbuch:
Distributed Shortest Paths Algorithms (Extended Abstract).
490-500

- Michael R. Fellows, Michael A. Langston:
On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract).
501-512

- Tomás Feder:
A New Fixed Point Approach for Stable Networks and Stable Marriages.
513-522

- Edith Cohen, Nimrod Megiddo:
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version).
523-534

- Avrim Blum:
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring).
535-542

- Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal:
Trading Space for Time in Undirected s-t Connectivity.
543-549

- Rajeev Motwani:
Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems.
550-561

- Allan Borodin, Walter L. Ruzzo, Martin Tompa:
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract).
562-573

- Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari:
The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract).
574-586

- Joel Friedman, Jeff Kahn, Endre Szemerédi:
On the Second Eigenvalue in Random Regular Graphs.
587-598

Last update Sun May 26 03:33:45 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page