21. STOC 1989: Seattle, Washigton, USA

• 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