# Lower bound for 3XOR and pairwise independent CSP’s

UCSD winter school on Sum-of-Squares, January 2017

### Mathematician’s serenity prayer

God,
Grant me the serenity to accept pathological counterexamples,
Courage to change my worldview given real counterexamples,
And wisdom to know the difference.

### Is Gaussian elimination pathological or real?

Of course it’s real but over finite fields very sensitive to noise

Intuition underlying lattice based cryptography.

Theorem: (Håstad’95) If $$P\neq NP$$ then $$\forall$$ efficient $$A$$ $$\exists$$ 3XOR polynomials $$\varphi,\varphi':{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi' \gt 1-o(1)$$, $$\max \varphi \lt 1/2+o(1)$$ but $$A(\varphi)=A(\varphi')$$.

Corollary: For all constant $$d$$, $$\exists$$ 3XOR polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ and $$d$$-pdist $$\mu$$ s.t. $$\max \varphi \lt 1/2+o(1)$$ but $${\tilde{\mathbb{E}}}_{\mu} \varphi \geq 1- o(1)$$.

(Improve to $$d=n^{0.9999}$$ under ETH - Moshkovits-Raz ’08)

Can we prove this unconditionally?

### Grigoriev’s Theorem (G’99,’01)

Theorem: (Unconditionally) $$\exists$$ 3XOR polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi \lt 0.51$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

• Even stronger than what we get from corollaries of NP hardness. In particular, SOS can’t simulate Gaussian elimination.
• Rules out “cubic sampling lemma”
• Result proven even before Parrilo and Lasserre papers defining sos!

### Generlization (B-Chan-Kothari’15)

Theorem: If $$P:{\{0,1\}}^k\rightarrow{\{0,1\}}$$ supports a pairwise independent distribution then $$\exists$$ $$P$$-polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi \lt {\mathbb{E}}_{U_k} P + 0.01$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

Without pairwise correlations, SOS can’t give any non trivial bounds.
Partial NP hardness results (Chan’13)

Unique Games Conjecture: Determine tradeoff of time vs. non triviality when correlations do exist.

### Proving Grigoriev’s Theorem

Theorem: $$\exists$$ 3XOR polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi \lt 0.51$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

Use random 3XOR instance $$I$$ of $$m=1000n$$ equations. . . .

For $$\ell=1..m$$, $$\ell^{th}$$ eq is $$\oplus_{i\in S_l} x_i = \sigma_\ell$$. . . .

$\varphi(x) = 1/2+\tfrac{1}{2m}\sum_{\ell=1}^m (-1)^{\sigma_\ell} \chi_{S_\ell}(x)$

for $$\chi_S = \prod_{i\in S}(1-2x_i)$$.

Lemma: $$\max_{x\in{\{0,1\}}^n} \varphi(x) \leq 0.51$$.

Proof: For every $$x$$, $${\mathbb{P}}_\varphi[ \varphi(x) \gt 1/2 + \epsilon ] \leq 2\exp(-\epsilon^2 m)$$.

Since $$m\gt n/100$$ the result follows. ∎

Proof simple but uses dreaded probabilistic method!

### Proving Grigoriev’s Theorem

Construct $$\mu$$ by defining $${\tilde{\mathbb{E}}}_\mu \chi_S$$ for all $$|S| \leq d = \Omega(n)$$.

Distribution very “random”, pretend to have $$\Omega(n)$$ entropy.

Challenge: No such dist over satisfying $$x$$’s.

Interpretation: $${\tilde{\mathbb{E}}}_\mu \chi_S$$ = bias for bet on whether $$\oplus_{i\in S}x_i = 1$$.

Intuition: (Max Entropy Principle) Comp. bounded obs. thinks $${\mathbb{P}}[\oplus_{i\in S}x_i = 1]=1/2$$ unless “obvious” linear relation.

Corollary: $${\tilde{\mathbb{E}}}\chi_S = \{-1,+1,0\} \Rightarrow {\mathbb{P}}[\oplus_{i\in S}x_i = 1]=\{1,0,1/2\}$$

($${\mathbb{P}}[\chi_T = 1]=1/2$$ unless proven otherwise)

### The Grigoriev Pseudodistribution

Input: Instance $$\{ \oplus_{i \in S_\ell} x_i = \sigma_\ell \}_{\ell=1}^m$$
Goal: Define $$d$$-pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $$\forall\ell {\tilde{\mathbb{E}}}_\mu \chi_{S_\ell} = (-1)^{\sigma_\ell}$$

1. $${\tilde{\mathbb{E}}}\chi_{S_\ell} := (-1)^{\sigma_\ell}$$ for all $$\ell \in [m]$$. (duh!)
1. while $$\exists$$ $$S,T$$ s.t. $${\tilde{\mathbb{E}}}\chi_S, {\tilde{\mathbb{E}}}\chi_T$$ defined, $$|S \oplus T| \leq d$$ and $${\tilde{\mathbb{E}}}\chi_{S\otimes T}$$ undefined: $${\tilde{\mathbb{E}}}\chi_{S\oplus T} := \left({\tilde{\mathbb{E}}}\chi_S \right)\left( {\tilde{\mathbb{E}}}\chi_T \right)$$

(If $${\mathbb{P}}[\chi_S=\sigma]=1$$ and $${\mathbb{P}}[\chi_T=\sigma']=1$$ then $${\mathbb{P}}[\chi_S\chi_T = \sigma\sigma']=1$$)

1. For every $$|T| \leq d$$ with $${\tilde{\mathbb{E}}}\chi_T$$ undefined, $${\tilde{\mathbb{E}}}\chi_T := 0$$.

($${\mathbb{P}}[\chi_T = 1]=1/2$$ unless proven otherwise)

### Analyzing Grigoriev Pdist

Input: Instance $$\{ \oplus_{i \in S_\ell} x_i = \sigma_\ell \}_{\ell=1}^m$$
1. $${\tilde{\mathbb{E}}}\chi_{S_\ell} := (-1)^{\sigma_\ell}$$ for all $$\ell \in [m]$$.
2. $${\tilde{\mathbb{E}}}\chi_{S \oplus T} = ({\tilde{\mathbb{E}}}\chi_S)({\tilde{\mathbb{E}}}\chi_T)$$, $$\forall |S|,|T|,|S \oplus T|\leq d$$.
3. $${\tilde{\mathbb{E}}}\chi_T = 0$$ otherwise.

Lemma 0: $${\tilde{\mathbb{E}}}\sum_{\ell=1}^m (-1)^{\sigma_\ell} \chi_{S_\ell} = m$$.

Lemma 1: If instance $$100d$$ expanding then pdist well defined.

Lemma 2: If pdist is well defined $${\tilde{\mathbb{E}}}p^2 \geq 0$$ $$\forall \leq d/2$$ deg $$p$$

### Analyzing Grigoriev Pdist (I)

Proof: Let $$T_1,T_2,\ldots$$ all sets in order of assigning $$\chi_{T_i}$$

Each $$T_i$$ is XOR is derived via $$\Delta_i$$ of underlying 3XOR’s, s.t. $$T_i = \oplus S\in\Delta_i$$.

Claim: $$|\Delta_i| \leq 10|T_i|$$.

Cor: If $$T_i=\emptyset$$ then $$\Delta_i=\emptyset$$

### Analyzing Grigoriev Pdist (II)

Proof: For $$|S|,|T| \leq d/2$$, def $$S \equiv T$$ iff $${\tilde{\mathbb{E}}}\chi_S\chi_T = {\tilde{\mathbb{E}}}\chi_{S\oplus T} \neq 0$$.

Write $$p = \sum_S \hat{p}(S)\chi_S$$, $$p=p_1+\ldots+p_k=0$$, all coeff’s of $$p_i$$ equivalent.

Claim: If $$i\neq j$$ then $${\tilde{\mathbb{E}}}p_ip_j =0$$

$$\Rightarrow$$ Suffices to show $${\tilde{\mathbb{E}}}p^2 \geq 0$$ where all $$S$$’s equivalent to $$S_0$$.

$$p = \chi_{S_0 }\sum_S \hat{p}(S)\chi_{S\oplus S_0}$$

$${\tilde{\mathbb{E}}}p^2 = \chi_{S_0}^2 \sum_{S,T} {\tilde{\mathbb{E}}}\chi_{S \oplus S_0}\chi_{T\oplus S_0}$$

$$=\sum_{S,T} \left({\tilde{\mathbb{E}}}\chi_{S \oplus S_0}\right) \left({\tilde{\mathbb{E}}}\chi_{T\oplus S_0}\right) = \left(\sum_S {\tilde{\mathbb{E}}}\chi_{S_0 \oplus S}\right)^2 \geq 0$$

### Extensions

Theorem: (Grigoriev’01) $$\exists$$ 3XOR polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi \lt 0.51$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

Theorem: (B-Chan-Kothari’14) If $$P:{\{0,1\}}^k\rightarrow{\{0,1\}}$$ supports a pairwise independent distribution then $$\exists$$ $$P$$-polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ s.t. $$\max \varphi \lt {\mathbb{E}}_{U_k} P + 0.01$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

Theorem: (Kothari-Mori-O’Donnell-Witmer’17) If $$P:{\{0,1\}}^k\rightarrow{\{0,1\}}$$ supports a $$t$$-wise independent distribution then for random $$P$$-polynomial $$\varphi:{\{0,1\}}^n\rightarrow [0,1]$$ with $$\tilde{O}(n^{(t+1)/2})$$ constraints w.h.p $$\max \varphi \lt {\mathbb{E}}_{U_k} P + 0.01$$ but $$\exists$$ $$\Omega(n)$$ pdist $$\mu$$ over $${\{0,1\}}^n$$ s.t. $${\tilde{\mathbb{E}}}_\mu \varphi = 1$$.

Pseudo-distribution: Marginal $$t$$-wise $$\rho$$ on the constraints, extend in natural way.

Analysis: “Local Gram-Schmidt”

### Reductions

Lemma: If $$\mu$$ is degree $$d$$ pdist and $$p:{\{0,1\}}^n\to{\{0,1\}}^m$$ is degree $$O(1)$$ poly, then $$\{ p(x) \}_{x \sim \mu}$$ is degree $$\Omega(d)$$ pdist.

Corollary: If $$3LIN_{0.99 \text{ vs } 0.51} \leq \Pi$$ via “gadget reduction” then $$\Pi$$ hard for $$\Omega(n)$$ deg SOS

Gadget reduction: The map $$\text{sol'n to 3LIN} \mapsto \text{sol'n to \Pi}$$ is local: every output bit depends on $$O(1)$$ inputs.

Applied to many problems to get SOS lowerbounds matching NP hardness results.

If ETH $$\Rightarrow$$ $$\Pi$$ requires $$n^{\Omega(d)}$$ time, then typically can show $$\Pi$$ requires $$\tilde{\Omega}(d)$$ SOS degree.

### Integarlity gap to reductions?

If ETH $$\Rightarrow$$ $$\Pi$$ requires $$n^{\Omega(d)}$$ time, then typically can show $$\Pi$$ requires $$\tilde{\Omega}(d)$$ SOS degree.

Is there inverse direction?

Only general result is Raghavendra’s.

One example: (Chan ‘13’) NP hardness matching SOS result for predicates containing pairwise indepenent subspace.

Opps, you cannot play draw N guess with this browser!