22. STOC 1990: Baltimore, Maryland, USA

• Michael L. Fredman, Dan E. Willard:
  BLASTING through the Information Theoretic Barrier with FUSION TREES. 1-7
  
• Richard Cole:
  On the Dynamic Finger Conjecture for Splay Trees (Extended Abstract). 8-17
  
• Rajamani Sundar, Robert Endre Tarjan:
  Unique Binary Search Tree Representations and Equality-testing of Sets and Sequences. 18-25
  
• Greg N. Frederickson:
  The Information Theory Bound Is Tight for Selection in a Heap. 26-33
  
• Johannes A. La Poutré:
  Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines. 34-44
  
• Wayne Goddard, Valerie King, Leonard J. Schulman:
  Optimal Randomized Algorithms for Local Sorting and Set-Maxima. 45-53
  
• Raymond A. Board, Leonard Pitt:
  On the Necessity of Occam Algorithms. 54-63
  
• Avrim Blum:
  Learning Boolean Functions in an Infinite Atribute Space (Extended Abstract). 64-72
  
• Manuel Blum, Michael Luby, Ronitt Rubinfeld:
  Self-Testing/Correcting with Applications to Numerical Problems. 73-83
  
• Andrew Chi-Chih Yao:
  Coherent Functions and Program Checkers (Extended Abstract). 84-94
  
• Shimon Even, Sergio Rajsbaum:
  The Use of a Synchronizer Yields Maximum Computation Rate in Distributed Networks (Extended Abstract). 95-105
  
• Michael J. Fischer, Shlomo Moran, Steven Rudich, Gadi Taubenfeld:
  The Wakeup Problem (Extended Abstract). 106-116
  
• Martin Dietzfelbinger, Friedhelm Meyer auf der Heide:
  How to Distribute a Dictionary in a Complete Network. 117-127
  
• Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal:
  Computing with Unreliable Information (Preliminary Version). 128-137
  
• Zvi M. Kedem, Krishna V. Palem, Paul G. Spirakis:
  Efficient Robust Parallel Computations (Extended Abstract). 138-148
  
• Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs:
  On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract). 149-158
  
• Jeffrey Scott Vitter, Elizabeth A. M. Shriver:
  Optimal Disk I/O with Parallel Block Transfer (Extended Abstract). 159-169
  
• Uzi Vishkin:
  Deterministic Sampling-A New Technique for Fast Pattern Matching. 170-180
  
• Ming-Yang Kao, Philip N. Klein:
  Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs. 181-192
  
• Robert Cypher, C. Greg Plaxton:
  Deterministic Sorting in Nearly Logarithmic Time on the Hypercube and Related Computers. 193-203
  
• Noam Nisan:
  Psuedorandom Generators for Space-Bounded Computation. 204-212
  
• Joseph Naor, Moni Naor:
  Small-bias Probability Spaces: Efficient Constructions and Applications. 213-223
  
• Jeanette P. Schmidt, Alan Siegel:
  The Analysis of Closed Hashing under Limited Randomness (Extended Abstract). 224-234
  
• Yishay Mansour, Noam Nisan, Prasoon Tiwari:
  The Computational Complexity of Universal Hashing. 235-243
  
• Joseph Gil, Friedhelm Meyer auf der Heide, Avi Wigderson:
  Not All Keys Can Be Hashed in Constant Time (Preliminary Version). 244-253
  
• David Zuckerman:
  A Technique for Lower Bounding the Cover Time. 254-259
  
• Nathan Linial, Noam Nisan:
  Approximate Inclusion-Exclusion. 260-270
  
• Richard Cleve:
  Towards Optimal Simulations of Formulas by Bounded-Width Programs. 271-277
  
• Mario Szegedy:
  Functions with Bounded Symmetric Communication Complexity and Circuits with \mathop mod m Gates. 278-286
  
• Ran Raz, Avi Wigderson:
  Monotone Circuits for Matching Require Linear Depth. 287-292
  
• Noga Alon, Paul D. Seymour, Robin Thomas:
  A Separator Theorem for Graphs with an Excluded Minor and its Applications. 293-299
  
• Gary L. Miller, William P. Thurston:
  Separators in Two and Three Dimensions. 300-309
  
• Philip N. Klein, Clifford Stein, Éva Tardos:
  Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities. 310-321
  
• Ketan Mulmuley:
  Output Sensitive Construction of Levels and Voronoi Diagrams in R^d of Order 1 to k. 322-330
  
• Alok Aggarwal, Mark Hansen, Frank Thomson Leighton:
  Solving Query-Retrieval Problems by Compacting Voronoi Diagrams (Extended Abstract). 331-340
  
• David G. Kirkpatrick, Bhubaneswar Mishra, Chee-Keng Yap:
  Quantitative Steinitz's Theorems with Applications to Multifingered Grasping. 341-351
  
• Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani:
  An Optimal Algorithm for On-line Bipartite Matching. 352-358
  
• Marshall W. Bern, Daniel H. Greene, Arvind Raghunathan, Madhu Sudan:
  Online Algorithms for Locating Checkpoints. 359-368
  
• Don Coppersmith, Peter Doyle, Prabhakar Raghavan, Marc Snir:
  Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version). 369-378
  
• Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, Avi Wigderson:
  On the Power of Randomization in Online Algorithms (Extended Abstract). 379-386
  
• John Rompel:
  One-Way Functions are Necessary and Sufficient for Secure Signatures. 387-394
  
• Johan Håstad:
  Pseudo-Random Generators under Uniform Assumptions. 395-404
  
• A. W. Schrift, Adi Shamir:
  The Discrete Log is Very Discreet. 405-415
  
• Uriel Feige, Adi Shamir:
  Witness Indistinguishable and Witness Hiding Protocols. 416-426
  
• Moni Naor, Moti Yung:
  Public-key Cryptosystems Provably Secure against Chosen Ciphertext Attacks. 427-437
  
• Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis:
  On the Complexity of Local Search (Extended Abstract). 438-445
  
• Alessandro Panconesi, Desh Ranjan:
  Quantifiers and Approximation (Extended Abstract). 446-456
  
• Mitsunori Ogiwara, Osamu Watanabe:
  On Polynomial Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets. 457-467
  
• A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn:
  The Undecidability of the Semi-Unification Problem (Preliminary Report). 468-476
  
• Tero Harju, Juhani Karhumäki:
  Decidability of the Multiplicity Equivalence of Multitape Finite Automata. 477-481
  
• Mihir Bellare, Silvio Micali, Rafail Ostrovsky:
  Perfect Zero-Knowledge in Constant Rounds. 482-493
  
• Mihir Bellare, Silvio Micali, Rafail Ostrovsky:
  The (True) Complexity of Statistical Zero Knowledge. 494-502
  
• Donald Beaver, Silvio Micali, Phillip Rogaway:
  The Round Complexity of Secure Protocols (Extended Abstract). 503-513
  
• Rafail Ostrovsky:
  Efficient Computation on Oblivious RAMs. 514-523
  
• William M. Kantor, Eugene M. Luks:
  Computing in Quotient Groups. 524-534
  
• Allan Borodin, Prasoon Tiwari:
  On the Decidability of Sparse Univariate Polynomial Interpolation (Preliminary Version). 535-545
  
• Victor Shoup:
  Searching for Primitive Roots in Finite Fields. 546-554
  
• Yagati N. Lakshman:
  On the Complexity of Computing a Gröbner Basis for the Radical of a Zero Dimensional Ideal. 555-563
  
• Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse, John M. Pollard:
  The Number Field Sieve. 564-572
  

Last update Sat May 18 19:50:30 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page