The question comes from the following paper I have been reading:

[1] Integrality Gaps for Sherali–Adams Relaxations. SODA'09. Moses Charikar, Konstantin Makarychev, Yury Makarychev.

Theorem 6.1 of [1] constructs an Unique Game instance that survive $n^\gamma$ rounds of Sherali-Adams lifting. This result is widely used in subsequent works for proving extension complexity lowerbounds, like the quasi-polynomial LB for $(2-\epsilon)$-approx Vertex Cover[2], or the super-polynomial LB for UG itself[3]. The construction is not hard, and I feel it should be correct, however I can't understand how the proof goes.

[2] No small linear program approximates vertex cover within a factor $2 - \epsilon$. FOCS'15.

[3] Lower bounds on the size of semidefinite programming relaxations. STOC'15.

For completeness, the theorem is stated below:

Theorem 6.1. Fix a number of labels $q=2^t$, a real $\delta\in(0,1)$ and let $\Delta=\lceil C(q/\delta)^2\rceil$ (for a sufficiently large constant $C$). Then for every positive $\epsilon$ there exists $\gamma$ depending on $\epsilon$ such that for every sufficiently large $n$ there exists an instance of Unique Games on $\Delta$-regular graph $G=(V,E)$ on $n$ vertices so that (i) The cost of the optimal solution is at most $1/q\cdot(1 +\delta)$. (ii)There exists a solution to the LP relaxation obtained after $r=n^\gamma$ rounds of Sherali–Adams of cost $(1−\epsilon)$.

What confuses me of the proof is the part showing the UG instance has optimal value at most $(1+\delta)/q$ w.h.p. It's an simple application of probabilistic method: first fix an arbitrary labeling $\ell:V\mapsto[q]$, then for each edge $(u,v)\in E$, sample a permutation $\pi_{uv}:[q]\mapsto[q]$ uniformly at random; and for different edges their $\pi$ are sampled independently. Then the paper claims that

... for a fixed assignment of labels, the expected fraction of satisfied constraints (where the expectation is taken only over random choices of $\pi_{uv}$) is $1/q$. By the Central Limit Theorem, the probability that the fraction of satisfied constraints deviates from the expectation by more than $\delta/q$ is $o(q^{−n})$. Since the total number of fixed assignments is $q^n$, by the union bound, the Unique Game is at most $(1+\delta)/q$ satisfiable with probability approaching 1.

Although it's not stated formally, I guess the above paragraph means the following: if we let $X^\ell_{uv}=\mathbf{1}[\pi_{uv}(\ell(u))=\ell(v)]$ be the indicator variable of the constraint on edge $(u,v)$, then all $X^\ell_{uv}$'s are i.i.d. Bernoulli random variables with mean $1/q$. Suppose $m=|E|=n\Delta/2$, and we let $S^\ell_m=\frac{1}{m}\sum_{(u,v)\in E}X^\ell_{uv}$ denote the sample mean, then the CLT says that $$\sqrt{m}(S^\ell_n-1/q)\overset{\text{ in distribution}}{\longrightarrow}\mathcal{N}(0,\sigma^2)$$ But the CLT only says the distribution is converged pointwise, i.e., for any constant $z>0$, $$\left|\Pr\left[\sqrt{m}(S^\ell_n-1/q)<z\right]-\Phi(z/\sigma)\right|=\epsilon_m$$ for some $\epsilon_m\to 0$ with $m\to\infty$. While to obtain the claimed deviation bound in the paper, one needs $z=\sqrt{m}\delta/q$ which grows with $m$. And that results in the following bound $$\Pr\left[\sqrt{m}(S^\ell_n-1/q)<\sqrt{m}\delta/q\right]<\Phi(\sqrt{m}\delta/(q\sigma))+\epsilon_m$$ But this is not $o(q^{-n})$ as claimed in the paper, since there's no guarantee for the decaying rate of $\epsilon_m$. Not sure if this is correct.

(I don't know why we can't use Chernoff bound directly to obtain the $o(q^{-n})$ rate. Since $m=n\Delta/2=Cn(q/\delta)^2/2$, the Chernoff bound produces a decaying rate of $\exp(-Cnq/2)$.)

Also, the statement of Theorem 6.1 (as well as its proof) seems to claim that the result holds for all $n>N$ for some $N$ depending on $q,\delta,\epsilon$. But I notice that when [2][3] cites this theorem, they instead use a weaker form "for infinitely many $n$". However, if we can use the stronger form, then [3]'s approach (specifically, Corollary 7.7 in [3]) can actually give a sub-exponential extension complexity LB for UG, rather than the much weaker super-polynomial LB currently stated in it. Any suggestions?


Your Answer

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

Browse other questions tagged or ask your own question.