Lesson 6

Let us give an example where practical benefits can be derived from the fact that 2-independence is a weaker property than mutual independence.

The maximum cut problem is a difficult algorithmic problem with applications in fields such as statistical physics, integrated circuit design, and image analysis. It requires finding a partition of the vertices in a given graph into two parts such that the number of edges connecting vertices from different parts is maximized.

If each vertex is assigned randomly and independently to one of the parts, then on average, \(m/2\) edges will be in the cut, where \(m\) is the number of edges. This implies that there always exists a cut of size at least \(m/2\). This immediately gives a simple probabilistic algorithm. But what if we want to quickly and deterministically find such a cut? We could enumerate the entire sample space, but its size is \(2^{n}\), where \(n=|V|\) is the number of vertices in the graph. It turns out that the size of the sample space can be significantly reduced. To estimate \(m/2\) (for the expected cut size), we only need pairwise independence. Suppose for simplicity that \(n=2^{d}\) and consider the field \(\mathbb{F}_{n}\). We choose random \(a,b \in \mathbb{F}_{n}\) and for each \(i \in [n]\) consider the random variable \(\alpha_{i}=a \cdot i + b\). It is easy to show that these random variables are pairwise independent: for any \(i \neq j\) and \(x,y \in \mathbb{F}_{n}\) it holds that \[\Pr[\alpha_{i}=x, \ \alpha_{j}=y]=\Pr[\alpha_{i}=x]\cdot\Pr[\alpha_{j}=y] = \frac{1}{n^2}\ .\] Indeed, for fixed \(i \neq j, x,y\), the system of equations \(\{ai+b=x, aj+b=y\}\) is always uniquely solvable in the field: \(a=(x-y)/(i-j)\), \(b=x-i(x-y)/(i-j)\). Then we proceed as follows: we choose \(a,b\), and then assign each vertex \(i \in [n]\) to a part corresponding to the first bit of the binary representation of \(\alpha_{i}\). The expected cut size remains \(m/2\), but now all sample outcomes can be easily enumerated (by iterating over all pairs \((a,b)\)).