1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – galah92 Jun 18 at 11:53
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jun 18 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.