---

Pairwise Independence

We will consider the well-known MAX-CUT problem and show that
a simple randomized algorithm works well (in expectation). But to
implement the algorithm we need "too many" pure random bits. Since pure
random bits are costly to generate, we will use only pairwise independent
bits and analyze the algorithm again. Finally we will show how to produce
pairwise independent bits efficiently.