22. STOC 1990: Baltimore, Maryland, USA
Harriet Ortiz (Ed.): Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA. ACM 1990 ISBN 0-89791-361-2- 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
- 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
- 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
- Noga Alon, Paul D. Seymour, Robin Thomas: A Separator Theorem for Graphs with an Excluded Minor and its Applications. 293-299
- 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
- Christos H. Papadimitriou, Alejandro A. Schäffer, Mihalis Yannakakis: On the Complexity of Local Search (Extended Abstract). 438-445
- 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: 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team