default search action
21st STOC 1989: Seattle, Washigton, USA
- David S. Johnson:
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 14-17, 1989, Seattle, Washington, USA. ACM 1989, ISBN 0-89791-307-8 - László Babai
, Noam Nisan
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract). 1-11 - Russell Impagliazzo
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
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
On omega-Automata and Temporal Logic (Preliminary Report). 127-137 - Doug Ierardi:
Quantifier Elimination in the Theory of an Algebraically-closed Field. 138-147 - (Withdrawn) 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
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
Lower Bounds on the Length of Universal Traversal Sequences (Detailed Abstract). 562-573 - Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-14 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: