22. STOC 1990
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA. ACM 1990
- 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
- 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
Copyright © Mon Nov 2 21:15:20 2009
by Michael Ley (ley@uni-trier.de)
