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.

Bibliography

AN96

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

FKG71

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

Spe90

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