Hadas Shachnai: Probabilistic Tools in the Analysis of Randomized Parallel Algorithms

We discuss two probabilistic tools that have been successfully applied in the analysis of randomized sequential algorithms, namely, $(i)$ the FKG inequality, and $(ii)$ deterministic construction of (almost) random permutations. We show how these tools can be applied to obtain efficient parallel algorithms for fundamental problems on (hyper)graphs.

Based on joint work with Aravind Srinivasan.


Noga Alon and Moni Naor.
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions.
Algorithmica, 16(4-5):434-449, 1996.

C. M. Fortuin, P. W. Kasteleyn, and Jean Ginibre.
Correlation inequalities on some partially ordered sets.
Comm. Math. Phys., 22:89-103, 1971.

Joel Spencer.
The probabilistic lens: Sperner, Turán and Bregman revisited.
In A tribute to Paul Erdos, pages 391-396. Cambridge Univ. Press, Cambridge, 1990.

Back to the Index

Please send comments and corrections to Thomas Klausner.