# Sherali-Adams lowerbound instance of Unique Games constructed via CLT

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) 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?