Lesson 3

Derandomization: the method of small sample spaces For the approximate algorithm for Maximum Cut, we proved that the random variable “number of cut edges” has a good expectation. From this, one can immediately conclude that there exists a point in the sample space where our random variable takes a sufficiently large value. However, the sample space in our case is \(\{0,1\}^{n}\), so simply iterating through all points in it is expensive. At the same time, looking more closely at the analysis, we notice that we only used pairwise independence. It turns out that if we only need pairwise independence, we can significantly reduce the number of random bits used and, accordingly, the size of the sample space.

For simplicity, let us assume that the set of graph vertices is \([n]\) and that \(n\) is a power of two (this is needed so that a field of size \(n\) exists and so that \(n\) is even). Consider the field \(\mathbb{F}_{n}\) and the \(2\)-universal family \(\mathcal{H}\) from Theorem above. We take a random hash function \(h \in \mathcal{H}\), which will determine the colors of all vertices: we color vertex \(i\) with the color \((h(i) \bmod 2)\). On average, half of the edges will be cut again, but the sample space \(\mathcal{H}\) now has size \(n^{2}\), so we can simply iterate through all its points.