Lower bound for 3XOR and pairwise independent CSP’s

Boaz Barak and David Steurer

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}$

${\tilde{\mathbb{E}}}\chi_{S_\ell} := (-1)^{\sigma_\ell}$ for all $\ell \in [m]$. (duh!)

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

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.