Journal of the ACM Bibliography

Categories and Subject Descriptors: F.1.2 [Computation by Abstract Devices]: Modes of Computation -- parallelism, probalistic computation; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.1 [Discrete Mathematics]: Combinatorics -- combinatorial algorithms; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Discrepancy, removing randomness

Selected papers that cite this one

• N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica, 16(4/5):434-449, October/November 1996.

• László Babai. Paul Erd\H{o}s (1913-1996): His influence on the theory of computing. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 383-401, El Paso, Texas, 4-6 May 1997.

• Bonnie Berger. The fourth moment method. SIAM Journal on Computing, 26(4):1188-1207, August 1997.

• Suresh Chari, Pankaj Rohatgi, and Aravind Srinivasan. Improved algorithms via approximations of probability distributions (extended abstract). In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 584-592, Montréal, Québec, Canada, 23-25 May 1994.

• Bernard Chazelle. Computational geometry: A restrospective. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 75-94, Montréal, Québec, Canada, 23-25 May 1994.

• Bernard Chazelle and Ji\v{r}í Matou\v{s}ek. On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21(3):579-597, November 1996.

• Devdatt Dubhashi, David A. Grable, and Alessandro Panconesi. Near-optimal, distributed edge colouring via the nibble method. Theoretical Computer Science, 203(2):225-251, 28 August 1998.

• David A. Grable and Alessandro Panconesi. Nearly optimal distributed edge colouring in O(log log n) rounds. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 278-285, New Orleans, Louisiana, 5-7 January 1997.

• David R. Karger and Daphne Koller. (De)randomized construction of small sample spaces in NC. Journal of Computer and System Sciences, 55(3):402-413, December 1997.

• Ji\v{r}í Matou\v{s}ek. Derandomization in computational geometry. Journal of Algorithms, 20(3):545-580, May 1996.

• Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, February 1996.

• Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing, 26(2):350-368, April 1997.

Selected references

• B. Awerbuch, A. Israeli, and Y. Shiloach. Finding Euler circuits in logarithmic parallel time. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pages 249-257, Washington, D.C., 1984.

• Benny Chor, Oded Goldreich, Johan Hastad, Joel Friedman, Steven Rudich, and Roman Smolensky. The bit extraction problem of t-resilient functions (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 396-407, Portland, Oregon, 21-23 October 1985. IEEE.

• Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on Boolean functions (extended abstract). In 29th Annual Symposium on Foundations of Computer Science, pages 68-80, White Plains, New York, 24-26 October 1988. IEEE.

• Michael Luby. Removing randomness in parallel computation without a processor penalty. In 29th Annual Symposium on Foundations of Computer Science, pages 162-173, White Plains, New York, 24-26 October 1988. IEEE.

• Rajeev Motwani, Joseph Naor, and Moni Naor. The probabilistic method yields deterministic parallel algorithms. In 30th Annual Symposium on Foundations of Computer Science, pages 8-13, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Michael O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989.

Shortcuts: