Randomness (and derandomization) in algorithm design

Randomization is a powerful and versatile technique in algorithm design. We describe a number of applications where it can be used for distributed algorithms, and combinatorial optimization. Among other advantages, it leads to complex coordination and load-balancing almost for free. Paradoxically, one of the most powerful uses of randomness is to get deterministic algorithms. These deterministic algorithms are, in turn, building blocks for other randomized algorithms. We describe some examples for hypergraph matching and the Lovasz Local Lemma. In the hypergraph matching algorithm, this maneuver is repeated twice --- we start with a simple randomized rounding algorithm that is derandomized. Combining this deterministic algorithm with an additional randomized sparsification step gives an exponentially more efficient randomized algorithm. Then this new randomized algorithm can itself be derandomized to give an exponentially more efficient deterministic algorithm. We conclude with discussions about applications to randomness in other areas including clustering, statistical physics, and future directions.