# Derandomize MAX-CUT problem using $\log n$ bits

Consider the MAX-CUT problem. We can flip $$n$$ coins to generate a random cut, and by linearity of expectation we get that with "good probability" our cut we'll be bigger then $$\frac{n}{2}$$.

Using pseudo random generators (XOR for example) we can generate $$n$$ pairwise independent bits from $$\log n$$ random bits. Using that approach, we can de-randomize the MAX-CUT problem with polynomial complexity.

With that algorithm, we are only checking $$n$$ possible cuts, where there are total of $$2^n$$. Is it promised that a "good" cut is within these $$n$$ cuts? Why?

Consider a graph with $$n$$ vertices and $$m$$ edges.
Let $$\mathcal{D}$$ be a pairwise independent distribution over $$\{0,1\}^n$$, and suppose that $$x = (x_1,\ldots,x_n) \sim \mathcal{D}$$. For every edge $$(i,j)$$, the probability that it is cut in the cut corresponding to $$x$$ is $$\Pr[x_i \neq x_j] = \frac{1}{2},$$ due to pairwise independence. Therefore the expected number of edges cut is exactly $$\frac{m}{2}$$, by linearity of expectation. In particular, there is at least one realization of $$x$$ (that is, one point in the support of $$\mathcal{D}$$) which cuts at least $$m/2$$ edges.
• Thanks. $\mathcal{D}$ is over $\{0,1\}^n$, which correspond to the algorithm that generates $n$ bits (and the de-randomized one loop over $2^n$ options). My Question is about the pseudo-random algorithm, which generate $\log n$ bits instead, and so loop over $n$ options. Why does it's support has a "good" cut, as well? – galah92 Jun 18 '19 at 11:53
• My answer is also about the pseudorandom distribution. The vector $x$ isn’t sampled uniformly. Rather, it is sample according to a pairwise uniform distribution $\mathcal D$. – Yuval Filmus Jun 18 '19 at 11:58