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