1
$\begingroup$

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?

$\endgroup$

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.