21. STOC 1989
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washigton, USA. ACM 1989
- László Babai, Noam Nisan, Mario Szegedy:
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract).
1-11 BibTeX
- Russell Impagliazzo, Leonid A. Levin, Michael Luby:
Pseudo-random Generation from one-way functions (Extended Abstracts).
12-24 BibTeX
- Oded Goldreich, Leonid A. Levin:
A Hard-Core Predicate for all One-Way Functions.
25-32 BibTeX
- Moni Naor, Moti Yung:
Universal One-Way Hash Functions and their Cryptographic Applications.
33-43 BibTeX
- Russell Impagliazzo, Steven Rudich:
Limits on the Provable Consequences of One-Way Permutations.
44-61 BibTeX
- Benny Chor, Eyal Kushilevitz:
A Zero-One Law for Boolean Privacy (extended abstract).
62-72 BibTeX
- Tal Rabin, Michael Ben-Or:
Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract).
73-85 BibTeX
- Manuel Blum, Sampath Kannan:
Designing Programs That Check Their Work.
86-97 BibTeX
- Brigitte Vallée:
Provably Fast Integer Factoring with Quasi-Uniform Small Quadratic Residues.
98-106 BibTeX
- Stephen A. Cook, Alasdair Urquhart:
Functional Interpretations of Feasibly Constructive Arithmetic (Extended Abstract).
107-112 BibTeX
- Foto N. Afrati, Stavros S. Cosmadakis:
Expressiveness of Restricted Recursive Queries (Extended Abstract).
113-126 BibTeX
- Shmuel Safra, Moshe Y. Vardi:
On omega-Automata and Temporal Logic (Preliminary Report).
127-137 BibTeX
- Doug Ierardi:
Quantifier Elimination in the Theory of an Algebraically-closed Field.
138-147 BibTeX
- Lance Fortnow, Michael Sipser:
Probabilistic Computation and Linear Time.
148-156 BibTeX
- Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer:
The Isomorphism Conjecture Fails Relative to a Random Oracle (Extended Abstract).
157-166 BibTeX
- Alexander A. Razborov:
On the Method of Approximations.
167-176 BibTeX
- Nader H. Bshouty:
On the Extended Direct Sum Conjecture.
177-185 BibTeX
- Andrew Chi-Chih Yao:
Circuits and Local Computation.
186-196 BibTeX
- Paul Beame:
A General Sequential Time-Space Tradeoff for Finding Unique Elements.
197-203 BibTeX
- Shai Ben-David, Benny Chor, Oded Goldreich, Michael Luby:
On the Theory of Average Case Complexity.
204-216 BibTeX
- Tak Wah Lam, Prasoon Tiwari, Martin Tompa:
Tradeoffs Between Communication and Space.
217-226 BibTeX
- 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 BibTeX
- Eli Upfal:
An O(log N) Deterministic Packet Routing Scheme (Preliminary Version).
241-250 BibTeX
- Johan Håstad, Frank Thomson Leighton, Mark Newman:
Fast Computation Using Faulty Hypercubes (Extended Abstract).
251-263 BibTeX
- John H. Reif, Stephen R. Tate:
Optimal Size Integer Division Circuits.
264-273 BibTeX
- Noga Alon, Amotz Bar-Noy, Nathan Linial, David Peleg:
On the Complexity of Radio Communication (Extended Abstract).
274-285 BibTeX
- Ming-Yang Kao, Gregory E. Shannon:
Local Reorientation, Global Order, and Planar Topology (Preliminary Version).
286-296 BibTeX
- Alok Aggarwal, Richard J. Anderson, Ming-Yang Kao:
Parallel Depth-First Search in General Directed Graphs (Preliminary Version).
297-308 BibTeX
- Omer Berkman, Dany Breslauer, Zvi Galil, Baruch Schieber, Uzi Vishkin:
Highly Parallelizable Problems (Extended Abstract).
309-319 BibTeX
- Ravi B. Boppana:
Optimal Separations Between Concurrent-Write Parallel Machines.
320-326 BibTeX
- Noam Nisan:
CREW PRAMs and Decision Trees.
327-335 BibTeX
- Amos Fiat, Moni Naor:
Implicit O(1) Probe Search.
336-344 BibTeX
- Michael L. Fredman, Michael E. Saks:
The Cell Probe Complexity of Dynamic Data Structures.
345-354 BibTeX
- Jeanette P. Schmidt, Alan Siegel:
On Aspects of Universality and Performance for Closed Hashing (Extended Abstract).
355-366 BibTeX
- Claire Kenyon-Mathieu, Valerie King:
Verifying Partial Orders.
367-374 BibTeX
- Martin E. Dyer, Alan M. Frieze, Ravi Kannan:
A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
375-381 BibTeX
- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir:
Lines in Space-Combinatorics, Algorithms and Applications.
382-393 BibTeX
- John H. Reif, Sandeep Sen:
Polling: A New Randomized Sampling Technique for Computational Geometry.
394-404 BibTeX
- Jacob E. Goodman, Richard Pollack, Bernd Sturmfels:
Coordinate Representation of Order Types Requires Exponential Storage.
405-410 BibTeX
- Ronald L. Rivest, Robert E. Schapire:
Inference of Finite Automata Using Homing Sequences (Extended Abstract).
411-420 BibTeX
- Leonard Pitt, Manfred K. Warmuth:
The Minimum Consistent DFA Problem Cannot Be Approximated within any Polynomial.
421-432 BibTeX
- Michael J. Kearns, Leslie G. Valiant:
Cryptographic Limitations on Learning Boolean Formulae and Finite Automata.
433-444 BibTeX
- Jean-Camille Birget:
Proof of a Conjecture of R. Kannan.
445-453 BibTeX
- Danny Dolev, Nir Shavit:
Bounded Concurrent Time-Stamp Systems Are Constructible.
454-466 BibTeX
- Ronald L. Graham, Andrew Chi-Chih Yao:
On the Improbability of Reaching Byzantine Agreements (Preliminary Version).
467-478 BibTeX
- Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, David Peleg:
Compact Distributed Data Structures for Adaptive Routing (Extended Abstract).
479-489 BibTeX
- Baruch Awerbuch:
Distributed Shortest Paths Algorithms (Extended Abstract).
490-500 BibTeX
- Michael R. Fellows, Michael A. Langston:
On Search, Decision and the Efficiency of Polynomial-Time Algorithms (Extended Abstract).
501-512 BibTeX
- Tomás Feder:
A New Fixed Point Approach for Stable Networks and Stable Marriages.
513-522 BibTeX
- Edith Cohen, Nimrod Megiddo:
Strongly Polynomial-Time and NC Algorithms for Detecting Cycles in Dynamic Graphs (Preliminary Version).
523-534 BibTeX
- Avrim Blum:
An \tildeO(n^0.4)-Approximation Algorithm for 3-Coloring (and Improved Approximation Algorithm for k-Coloring).
535-542 BibTeX
- Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal:
Trading Space for Time in Undirected s-t Connectivity.
543-549 BibTeX
- Rajeev Motwani:
Expanding Graphs and the Average-case Analysis of Algorithms for Matchings and Related Problems.
550-561 BibTeX
- Allan Borodin, Walter L. Ruzzo, Martin Tompa:
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract).
562-573 BibTeX
- 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 BibTeX
- Joel Friedman, Jeff Kahn, Endre Szemerédi:
On the Second Eigenvalue in Random Regular Graphs.
587-598 BibTeX
Copyright © Sat May 16 23:43:10 2009
by Michael Ley (ley@uni-trier.de)
