$
\newcommand{\undefined}{}
\newcommand{\hfill}{}
\newcommand{\qedhere}{\square}
\newcommand{\qed}{\square}
\newcommand{\ensuremath}[1]{#1}
\newcommand{\bit}{\{0,1\}}
\newcommand{\Bit}{\{-1,1\}}
\newcommand{\Stab}{\mathbf{Stab}}
\newcommand{\NS}{\mathbf{NS}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bs}{\mathbf{s}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\Var}{\mathbf{Var}}
\newcommand{\dist}{\text{dist}}
\newcommand{\norm}[1]{\\|#1\\|}
\newcommand{\etal}
\newcommand{\ie}
\newcommand{\eg}
\newcommand{\cf}
\newcommand{\rank}{\text{rank}}
\newcommand{\tr}{\text{tr}}
\newcommand{\mor}{\text{Mor}}
\newcommand{\hom}{\text{Hom}}
\newcommand{\id}{\text{id}}
\newcommand{\obj}{\text{obj}}
\newcommand{\pr}{\text{pr}}
\newcommand{\ker}{\text{ker}}
\newcommand{\coker}{\text{coker}}
\newcommand{\im}{\text{im}}
\newcommand{\vol}{\text{vol}}
\newcommand{\disc}{\text{disc}}
\newcommand{\bbA}{\mathbb A}
\newcommand{\bbB}{\mathbb B}
\newcommand{\bbC}{\mathbb C}
\newcommand{\bbD}{\mathbb D}
\newcommand{\bbE}{\mathbb E}
\newcommand{\bbF}{\mathbb F}
\newcommand{\bbG}{\mathbb G}
\newcommand{\bbH}{\mathbb H}
\newcommand{\bbI}{\mathbb I}
\newcommand{\bbJ}{\mathbb J}
\newcommand{\bbK}{\mathbb K}
\newcommand{\bbL}{\mathbb L}
\newcommand{\bbM}{\mathbb M}
\newcommand{\bbN}{\mathbb N}
\newcommand{\bbO}{\mathbb O}
\newcommand{\bbP}{\mathbb P}
\newcommand{\bbQ}{\mathbb Q}
\newcommand{\bbR}{\mathbb R}
\newcommand{\bbS}{\mathbb S}
\newcommand{\bbT}{\mathbb T}
\newcommand{\bbU}{\mathbb U}
\newcommand{\bbV}{\mathbb V}
\newcommand{\bbW}{\mathbb W}
\newcommand{\bbX}{\mathbb X}
\newcommand{\bbY}{\mathbb Y}
\newcommand{\bbZ}{\mathbb Z}
\newcommand{\sA}{\mathscr A}
\newcommand{\sB}{\mathscr B}
\newcommand{\sC}{\mathscr C}
\newcommand{\sD}{\mathscr D}
\newcommand{\sE}{\mathscr E}
\newcommand{\sF}{\mathscr F}
\newcommand{\sG}{\mathscr G}
\newcommand{\sH}{\mathscr H}
\newcommand{\sI}{\mathscr I}
\newcommand{\sJ}{\mathscr J}
\newcommand{\sK}{\mathscr K}
\newcommand{\sL}{\mathscr L}
\newcommand{\sM}{\mathscr M}
\newcommand{\sN}{\mathscr N}
\newcommand{\sO}{\mathscr O}
\newcommand{\sP}{\mathscr P}
\newcommand{\sQ}{\mathscr Q}
\newcommand{\sR}{\mathscr R}
\newcommand{\sS}{\mathscr S}
\newcommand{\sT}{\mathscr T}
\newcommand{\sU}{\mathscr U}
\newcommand{\sV}{\mathscr V}
\newcommand{\sW}{\mathscr W}
\newcommand{\sX}{\mathscr X}
\newcommand{\sY}{\mathscr Y}
\newcommand{\sZ}{\mathscr Z}
\newcommand{\sfA}{\mathsf A}
\newcommand{\sfB}{\mathsf B}
\newcommand{\sfC}{\mathsf C}
\newcommand{\sfD}{\mathsf D}
\newcommand{\sfE}{\mathsf E}
\newcommand{\sfF}{\mathsf F}
\newcommand{\sfG}{\mathsf G}
\newcommand{\sfH}{\mathsf H}
\newcommand{\sfI}{\mathsf I}
\newcommand{\sfJ}{\mathsf J}
\newcommand{\sfK}{\mathsf K}
\newcommand{\sfL}{\mathsf L}
\newcommand{\sfM}{\mathsf M}
\newcommand{\sfN}{\mathsf N}
\newcommand{\sfO}{\mathsf O}
\newcommand{\sfP}{\mathsf P}
\newcommand{\sfQ}{\mathsf Q}
\newcommand{\sfR}{\mathsf R}
\newcommand{\sfS}{\mathsf S}
\newcommand{\sfT}{\mathsf T}
\newcommand{\sfU}{\mathsf U}
\newcommand{\sfV}{\mathsf V}
\newcommand{\sfW}{\mathsf W}
\newcommand{\sfX}{\mathsf X}
\newcommand{\sfY}{\mathsf Y}
\newcommand{\sfZ}{\mathsf Z}
\newcommand{\cA}{\mathcal A}
\newcommand{\cB}{\mathcal B}
\newcommand{\cC}{\mathcal C}
\newcommand{\cD}{\mathcal D}
\newcommand{\cE}{\mathcal E}
\newcommand{\cF}{\mathcal F}
\newcommand{\cG}{\mathcal G}
\newcommand{\cH}{\mathcal H}
\newcommand{\cI}{\mathcal I}
\newcommand{\cJ}{\mathcal J}
\newcommand{\cK}{\mathcal K}
\newcommand{\cL}{\mathcal L}
\newcommand{\cM}{\mathcal M}
\newcommand{\cN}{\mathcal N}
\newcommand{\cO}{\mathcal O}
\newcommand{\cP}{\mathcal P}
\newcommand{\cQ}{\mathcal Q}
\newcommand{\cR}{\mathcal R}
\newcommand{\cS}{\mathcal S}
\newcommand{\cT}{\mathcal T}
\newcommand{\cU}{\mathcal U}
\newcommand{\cV}{\mathcal V}
\newcommand{\cW}{\mathcal W}
\newcommand{\cX}{\mathcal X}
\newcommand{\cY}{\mathcal Y}
\newcommand{\cZ}{\mathcal Z}
\newcommand{\bfA}{\mathbf A}
\newcommand{\bfB}{\mathbf B}
\newcommand{\bfC}{\mathbf C}
\newcommand{\bfD}{\mathbf D}
\newcommand{\bfE}{\mathbf E}
\newcommand{\bfF}{\mathbf F}
\newcommand{\bfG}{\mathbf G}
\newcommand{\bfH}{\mathbf H}
\newcommand{\bfI}{\mathbf I}
\newcommand{\bfJ}{\mathbf J}
\newcommand{\bfK}{\mathbf K}
\newcommand{\bfL}{\mathbf L}
\newcommand{\bfM}{\mathbf M}
\newcommand{\bfN}{\mathbf N}
\newcommand{\bfO}{\mathbf O}
\newcommand{\bfP}{\mathbf P}
\newcommand{\bfQ}{\mathbf Q}
\newcommand{\bfR}{\mathbf R}
\newcommand{\bfS}{\mathbf S}
\newcommand{\bfT}{\mathbf T}
\newcommand{\bfU}{\mathbf U}
\newcommand{\bfV}{\mathbf V}
\newcommand{\bfW}{\mathbf W}
\newcommand{\bfX}{\mathbf X}
\newcommand{\bfY}{\mathbf Y}
\newcommand{\bfZ}{\mathbf Z}
\newcommand{\rmA}{\mathrm A}
\newcommand{\rmB}{\mathrm B}
\newcommand{\rmC}{\mathrm C}
\newcommand{\rmD}{\mathrm D}
\newcommand{\rmE}{\mathrm E}
\newcommand{\rmF}{\mathrm F}
\newcommand{\rmG}{\mathrm G}
\newcommand{\rmH}{\mathrm H}
\newcommand{\rmI}{\mathrm I}
\newcommand{\rmJ}{\mathrm J}
\newcommand{\rmK}{\mathrm K}
\newcommand{\rmL}{\mathrm L}
\newcommand{\rmM}{\mathrm M}
\newcommand{\rmN}{\mathrm N}
\newcommand{\rmO}{\mathrm O}
\newcommand{\rmP}{\mathrm P}
\newcommand{\rmQ}{\mathrm Q}
\newcommand{\rmR}{\mathrm R}
\newcommand{\rmS}{\mathrm S}
\newcommand{\rmT}{\mathrm T}
\newcommand{\rmU}{\mathrm U}
\newcommand{\rmV}{\mathrm V}
\newcommand{\rmW}{\mathrm W}
\newcommand{\rmX}{\mathrm X}
\newcommand{\rmY}{\mathrm Y}
\newcommand{\rmZ}{\mathrm Z}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\paren}[1]{( #1 )}
\newcommand{\Paren}[1]{\left( #1 \right)}
\newcommand{\bigparen}[1]{\bigl( #1 \bigr)}
\newcommand{\Bigparen}[1]{\Bigl( #1 \Bigr)}
\newcommand{\biggparen}[1]{\biggl( #1 \biggr)}
\newcommand{\Biggparen}[1]{\Biggl( #1 \Biggr)}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\Abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\bigabs}[1]{\bigl\lvert #1 \bigr\rvert}
\newcommand{\Bigabs}[1]{\Bigl\lvert #1 \Bigr\rvert}
\newcommand{\biggabs}[1]{\biggl\lvert #1 \biggr\rvert}
\newcommand{\Biggabs}[1]{\Biggl\lvert #1 \Biggr\rvert}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\Card}[1]{\left\lvert #1 \right\rvert}
\newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert}
\newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert}
\newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert}
\newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\Norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert}
\newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert}
\newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert}
\newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\Iprod}[1]{\left\langle #1 \right\rangle}
\newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle}
\newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle}
\newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle}
\newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle}
\newcommand{\set}[1]{\lbrace #1 \rbrace}
\newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace}
\newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace}
\newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace}
\newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace}
\newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace}
\newcommand{\bracket}[1]{\lbrack #1 \rbrack}
\newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack}
\newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack}
\newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack}
\newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack}
\newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack}
\newcommand{\ucorner}[1]{\ulcorner #1 \urcorner}
\newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner}
\newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner}
\newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner}
\newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner}
\newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil}
\newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil}
\newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil}
\newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor}
\newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor}
\newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor}
\newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor}
\newcommand{\lcorner}[1]{\llcorner #1 \lrcorner}
\newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner}
\newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner}
\newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner}
\newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner}
\newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner}
\newcommand{\ket}[1]{| #1 \rangle}
\newcommand{\bra}[1]{\langle #1 |}
\newcommand{\braket}[2]{\langle #1 | #2 \rangle}
\newcommand{\ketbra}[1]{| #1 \rangle\langle #1 |}
\newcommand{\e}{\varepsilon}
\newcommand{\eps}{\varepsilon}
\newcommand{\from}{\colon}
\newcommand{\super}[2]{#1^{(#2)}}
\newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}}
\newcommand{\tensor}{\otimes}
\newcommand{\eset}{\emptyset}
\newcommand{\sse}{\subseteq}
\newcommand{\sst}{\substack}
\newcommand{\ot}{\otimes}
\newcommand{\Esst}[1]{\bbE_{\substack{#1}}}
\newcommand{\vbig}{\vphantom{\bigoplus}}
\newcommand{\seteq}{\mathrel{\mathop:}=}
\newcommand{\defeq}{\stackrel{\mathrm{def}}=}
\newcommand{\Mid}{\mathrel{}\middle|\mathrel{}}
\newcommand{\Ind}{\mathbf 1}
\newcommand{\bits}{\{0,1\}}
\newcommand{\sbits}{\{\pm 1\}}
\newcommand{\R}{\mathbb R}
\newcommand{\Rnn}{\R_{\ge 0}}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newcommand{\A}{\mathbb A}
\newcommand{\Real}{\mathbb R}
\newcommand{\mper}{\,.}
\newcommand{\mcom}{\,,}
\DeclareMathOperator{\Id}{Id}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\vol}{vol}
\DeclareMathOperator{\val}{val}
\DeclareMathOperator{\opt}{opt}
\DeclareMathOperator{\Opt}{Opt}
\DeclareMathOperator{\Val}{Val}
\DeclareMathOperator{\LP}{LP}
\DeclareMathOperator{\SDP}{SDP}
\DeclareMathOperator{\Tr}{Tr}
\DeclareMathOperator{\Inf}{Inf}
\DeclareMathOperator{\size}{size}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\min}{min}
\DeclareMathOperator{\max}{max}
\DeclareMathOperator{\argmax}{arg\,max}
\DeclareMathOperator{\argmin}{arg\,min}
\DeclareMathOperator{\qpoly}{qpoly}
\DeclareMathOperator{\qqpoly}{qqpoly}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\Conv}{Conv}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\perm}{perm}
\DeclareMathOperator{\mspan}{span}
\DeclareMathOperator{\mrank}{rank}
\DeclareMathOperator{\E}{\mathbb E}
\DeclareMathOperator{\pE}{\tilde{\mathbb E}}
\DeclareMathOperator{\Pr}{\mathbb P}
\DeclareMathOperator{\Span}{Span}
\DeclareMathOperator{\Cone}{Cone}
\DeclareMathOperator{\junta}{junta}
\DeclareMathOperator{\NSS}{NSS}
\DeclareMathOperator{\SA}{SA}
\DeclareMathOperator{\SOS}{SOS}
\DeclareMathOperator{\Stab}{\mathbf Stab}
\DeclareMathOperator{\Det}{\textbf{Det}}
\DeclareMathOperator{\Perm}{\textbf{Perm}}
\DeclareMathOperator{\Sym}{\textbf{Sym}}
\DeclareMathOperator{\Pow}{\textbf{Pow}}
\DeclareMathOperator{\Gal}{\textbf{Gal}}
\DeclareMathOperator{\Aut}{\textbf{Aut}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\cE}{\mathcal{E}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\pE}{\tilde{\mathbb{E}}}
\newcommand{\N}{\mathbb{N}}
\renewcommand{\P}{\mathcal{P}}
\notag
$
$
\newcommand{\sleq}{\ensuremath{\preceq}}
\newcommand{\sgeq}{\ensuremath{\succeq}}
\newcommand{\diag}{\ensuremath{\mathrm{diag}}}
\newcommand{\support}{\ensuremath{\mathrm{support}}}
\newcommand{\zo}{\ensuremath{\{0,1\}}}
\newcommand{\pmo}{\ensuremath{\{\pm 1\}}}
\newcommand{\uppersos}{\ensuremath{\overline{\mathrm{sos}}}}
\newcommand{\lambdamax}{\ensuremath{\lambda_{\mathrm{max}}}}
\newcommand{\rank}{\ensuremath{\mathrm{rank}}}
\newcommand{\Mslow}{\ensuremath{M_{\mathrm{slow}}}}
\newcommand{\Mfast}{\ensuremath{M_{\mathrm{fast}}}}
\newcommand{\Mdiag}{\ensuremath{M_{\mathrm{diag}}}}
\newcommand{\Mcross}{\ensuremath{M_{\mathrm{cross}}}}
\newcommand{\eqdef}{\ensuremath{ =^{def}}}
\newcommand{\threshold}{\ensuremath{\mathrm{threshold}}}
\newcommand{\vbls}{\ensuremath{\mathrm{vbls}}}
\newcommand{\cons}{\ensuremath{\mathrm{cons}}}
\newcommand{\edges}{\ensuremath{\mathrm{edges}}}
\newcommand{\cl}{\ensuremath{\mathrm{cl}}}
\newcommand{\xor}{\ensuremath{\oplus}}
\newcommand{\1}{\ensuremath{\mathrm{1}}}
\notag
$
$
\newcommand{\transpose}[1]{\ensuremath{#1{}^{\mkern-2mu\intercal}}}
\newcommand{\dyad}[1]{\ensuremath{#1#1{}^{\mkern-2mu\intercal}}}
\newcommand{\nchoose}[1]{\ensuremath}
\newcommand{\generated}[1]{\ensuremath{\langle #1 \rangle}}
\notag
$
$
\newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}}
\newcommand{\R} % real numbers
\newcommand{\N}} % natural numbers
\newcommand{\Z} % integers
\newcommand{\F} % a field
\newcommand{\Q} % the rationals
\newcommand{\C}{\mathbb{C}} % the complexes
\newcommand{\poly}}
\newcommand{\polylog}}
\newcommand{\loglog}}}
\newcommand{\zo}{\{0,1\}}
\newcommand{\suchthat}
\newcommand{\pr}[1]{\Pr\left[#1\right]}
\newcommand{\deffont}{\em}
\newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}}
\newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation
\newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance
\newcommand{\xor}{\oplus}
\newcommand{\GF}{\mathrm{GF}}
\newcommand{\eps}{\varepsilon}
\notag
$
$
\newcommand{\class}[1]{\mathbf{#1}}
\newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements
\newcommand{\BPP}{\class{BPP}}
\newcommand{\NP}{\class{NP}}
\newcommand{\RP}{\class{RP}}
\newcommand{\coRP}{\coclass{RP}}
\newcommand{\ZPP}{\class{ZPP}}
\newcommand{\BQP}{\class{BQP}}
\newcommand{\FP}{\class{FP}}
\newcommand{\QP}{\class{QuasiP}}
\newcommand{\VF}{\class{VF}}
\newcommand{\VBP}{\class{VBP}}
\newcommand{\VP}{\class{VP}}
\newcommand{\VNP}{\class{VNP}}
\newcommand{\RNC}{\class{RNC}}
\newcommand{\RL}{\class{RL}}
\newcommand{\BPL}{\class{BPL}}
\newcommand{\coRL}{\coclass{RL}}
\newcommand{\IP}{\class{IP}}
\newcommand{\AM}{\class{AM}}
\newcommand{\MA}{\class{MA}}
\newcommand{\QMA}{\class{QMA}}
\newcommand{\SBP}{\class{SBP}}
\newcommand{\coAM}{\class{coAM}}
\newcommand{\coMA}{\class{coMA}}
\renewcommand{\P}{\class{P}}
\newcommand\prBPP{\class{prBPP}}
\newcommand\prRP{\class{prRP}}
\newcommand\prP{\class{prP}}
\newcommand{\Ppoly}{\class{P/poly}}
\newcommand{\NPpoly}{\class{NP/poly}}
\newcommand{\coNPpoly}{\class{coNP/poly}}
\newcommand{\DTIME}{\class{DTIME}}
\newcommand{\TIME}{\class{TIME}}
\newcommand{\SIZE}{\class{SIZE}}
\newcommand{\SPACE}{\class{SPACE}}
\newcommand{\ETIME}{\class{E}}
\newcommand{\BPTIME}{\class{BPTIME}}
\newcommand{\RPTIME}{\class{RPTIME}}
\newcommand{\ZPTIME}{\class{ZPTIME}}
\newcommand{\EXP}{\class{EXP}}
\newcommand{\ZPEXP}{\class{ZPEXP}}
\newcommand{\RPEXP}{\class{RPEXP}}
\newcommand{\BPEXP}{\class{BPEXP}}
\newcommand{\SUBEXP}{\class{SUBEXP}}
\newcommand{\NTIME}{\class{NTIME}}
\newcommand{\NL}{\class{NL}}
\renewcommand{\L}{\class{L}}
\newcommand{\NQP}{\class{NQP}}
\newcommand{\NEXP}{\class{NEXP}}
\newcommand{\coNEXP}{\coclass{NEXP}}
\newcommand{\NPSPACE}{\class{NPSPACE}}
\newcommand{\PSPACE}{\class{PSPACE}}
\newcommand{\NSPACE}{\class{NSPACE}}
\newcommand{\coNSPACE}{\coclass{NSPACE}}
\newcommand{\coL}{\coclass{L}}
\newcommand{\coP}{\coclass{P}}
\newcommand{\coNP}{\coclass{NP}}
\newcommand{\coNL}{\coclass{NL}}
\newcommand{\coNPSPACE}{\coclass{NPSPACE}}
\newcommand{\APSPACE}{\class{APSPACE}}
\newcommand{\LINSPACE}{\class{LINSPACE}}
\newcommand{\qP}{\class{\tilde{P}}}
\newcommand{\PH}{\class{PH}}
\newcommand{\EXPSPACE}{\class{EXPSPACE}}
\newcommand{\SigmaTIME}[1]{\class{\Sigma_{#1}TIME}}
\newcommand{\PiTIME}[1]{\class{\Pi_{#1}TIME}}
\newcommand{\SigmaP}[1]{\class{\Sigma_{#1}P}}
\newcommand{\PiP}[1]{\class{\Pi_{#1}P}}
\newcommand{\DeltaP}[1]{\class{\Delta_{#1}P}}
\newcommand{\ATIME}{\class{ATIME}}
\newcommand{\ASPACE}{\class{ASPACE}}
\newcommand{\AP}{\class{AP}}
\newcommand{\AL}{\class{AL}}
\newcommand{\APSPACE}{\class{APSPACE}}
\newcommand{\VNC}[1]{\class{VNC^{#1}}}
\newcommand{\NC}[1]{\class{NC^{#1}}}
\newcommand{\AC}[1]{\class{AC^{#1}}}
\newcommand{\ACC}[1]{\class{ACC^{#1}}}
\newcommand{\TC}[1]{\class{TC^{#1}}}
\newcommand{\ShP}{\class{\# P}}
\newcommand{\PaP}{\class{\oplus P}}
\newcommand{\PCP}{\class{PCP}}
\newcommand{\kMIP}[1]{\class{#1\mbox{-}MIP}}
\newcommand{\MIP}{\class{MIP}}
$
$
\newcommand{\textprob}[1]{\text{#1}}
\newcommand{\mathprob}[1]{\textbf{#1}}
\newcommand{\Satisfiability}{\textprob{Satisfiability}}
\newcommand{\SAT}{\textprob{SAT}}
\newcommand{\TSAT}{\textprob{3SAT}}
\newcommand{\USAT}{\textprob{USAT}}
\newcommand{\UNSAT}{\textprob{UNSAT}}
\newcommand{\QPSAT}{\textprob{QPSAT}}
\newcommand{\TQBF}{\textprob{TQBF}}
\newcommand{\LinProg}{\textprob{Linear Programming}}
\newcommand{\LP}{\mathprob{LP}}
\newcommand{\Factor}{\textprob{Factoring}}
\newcommand{\CircVal}{\textprob{Circuit Value}}
\newcommand{\CVAL}{\mathprob{CVAL}}
\newcommand{\CircSat}{\textprob{Circuit Satisfiability}}
\newcommand{\CSAT}{\textprob{CSAT}}
\newcommand{\CycleCovers}{\textprob{Cycle Covers}}
\newcommand{\MonCircVal}{\textprob{Monotone Circuit Value}}
\newcommand{\Reachability}{\textprob{Reachability}}
\newcommand{\Unreachability}{\textprob{Unreachability}}
\newcommand{\RCH}{\mathprob{RCH}}
\newcommand{\BddHalt}{\textprob{Bounded Halting}}
\newcommand{\BH}{\mathprob{BH}}
\newcommand{\DiscreteLog}{\textprob{Discrete Log}}
\newcommand{\REE}{\mathprob{REE}}
\newcommand{\QBF}{\mathprob{QBF}}
\newcommand{\MCSP}{\mathprob{MCSP}}
\newcommand{\GGEO}{\mathprob{GGEO}}
\newcommand{\CKTMIN}{\mathprob{CKT-MIN}}
\newcommand{\MINCKT}{\mathprob{MIN-CKT}}
\newcommand{\IdentityTest}{\textprob{Identity Testing}}
\newcommand{\Majority}{\textprob{Majority}}
\newcommand{\CountIndSets}{\textprob{\#Independent Sets}}
\newcommand{\Parity}{\textprob{Parity}}
\newcommand{\Clique}{\textprob{Clique}}
\newcommand{\CountCycles}{\textprob{#Cycles}}
\newcommand{\CountPerfMatchings}{\textprob{\#Perfect Matchings}}
\newcommand{\CountMatchings}{\textprob{\#Matchings}}
\newcommand{\CountMatch}{\mathprob{\#Matchings}}
\newcommand{\ECSAT}{\mathprob{E#SAT}}
\newcommand{\ShSAT}{\mathprob{#SAT}}
\newcommand{\ShTSAT}{\mathprob{#3SAT}}
\newcommand{\HamCycle}{\textprob{Hamiltonian Cycle}}
\newcommand{\Permanent}{\textprob{Permanent}}
\newcommand{\ModPermanent}{\textprob{Modular Permanent}}
\newcommand{\GraphNoniso}{\textprob{Graph Nonisomorphism}}
\newcommand{\GI}{\mathprob{GI}}
\newcommand{\GNI}{\mathprob{GNI}}
\newcommand{\GraphIso}{\textprob{Graph Isomorphism}}
\newcommand{\QuantBoolForm}{\textprob{Quantified Boolean
Formulae}}
\newcommand{\GenGeography}{\textprob{Generalized Geography}}
\newcommand{\MAXTSAT}{\mathprob{Max3SAT}}
\newcommand{\GapMaxTSAT}{\mathprob{GapMax3SAT}}
\newcommand{\ELIN}{\mathprob{E3LIN2}}
\newcommand{\CSP}{\mathprob{CSP}}
\newcommand{\Lin}{\mathprob{Lin}}
\newcommand{\ONE}{\mathbf{ONE}}
\newcommand{\ZERO}{\mathbf{ZERO}}
\newcommand{\yes}
\newcommand{\no}
$
Basic Circuit Complexity
Introduction
Different from Turing machine, circuit Complexity is a nonuniform computation model that contains a family of boolean circuits for different input length. Concretely, we define:
Definition and motivation
A circuit family $C=\{C_i\}_{i\in\mathbb{N}}$ computes a function $f:{0,1}^* \rightarrow\{0,1\}$ if for any $x\in\{0,1\}^* $, $C_{|x|}(x)=f(x)$.
An analogy to compare the difference of Turing machine and circuit complexity is thinking a Turing machine as a powerful human brain while thinking circuit family as a collection of fly brains. Although Turing machine seems to have more power comparing to a single circuit, when gathering circuits as a family for each input size, the difference of computational power between them becomes nontrivial.
Also, a nature motivation to study circuit is that in real life application, we probably don’t care about infinitely growing input size. For instance, maybe solving $\TSAT$ of size 1,000,000,000 is enough.
Complexity measures
Previously, we consider different resources such as time, space, and alternation in Turing machine to see the computational power and tradeoff among them.
Here for circuit, we also identify several useful complexity measures that help us analyze its computational power.
- Size: The number of gates (sometimes we use wires) of the circuit.
- Depth: The largest number of gates from the input to the output.
- Type of gates: Common gates are AND, OR, NOT, MOD, MAJ.
- Fan-in of gates: Constant/Polynomial/Unbounded.
According to different settings of the complexity measures, we have the following common circuit complexity classes.
- $\Ppoly$: The size is polynomial and use fan-in 2 AND, OR, and NOT gates.
- $\NC{k}$: The size is polynomial and the depth is $O(\log^k n)$ and use fan-in 2 AND, OR, and NOT gates.
- $\AC{k}$: Basically the same as $\NC[k]$ except that the fan-in of AND and OR gates can be unbounded.
In this section, we are going to see several elementary results in the connection of circuit complexity class and the uniform complexity classes we introduced before.
There are two directions:
- What kind of uniform complexity classes being captured by $\Ppoly$.
- Turing machine with advice = Circuit family
- $\P\in\Ppoly$
- $\BPP\in\Ppoly$
- What kind of circuit family being captured by uniform complexity classes such as $\P$?
- $\P$-uniform
- logspace-uniform
Turing machine that takes advice
We define Turing machine with advice as follows.
Consider Turing machine $M$ with advice $\{a_i\}_{i\in\mathbb{N}}$ where $|a_i|\leq f(i)$. We say a language $L$ is decided by $M$ with advice $\{a_i\}_{i\in\mathbb{N}}$ if for any $x\in\{0,1\}^* $, $x\in L$ iff $M(x,a_{|x|})=1$.
It turns out that circuit family is equivalent to Turing machine with advice.
$L\in\Ppoly$ iff $L$ can be decided by a Turing machine with polynomial size advice in poly-time.
- ($\Rightarrow$)
Simply treat the circuits as advice and use a Turing machine to simulate the evaluation process. Clearly that both the advice and evaluation time are polynomial w.r.t. to input size.
- ($\Leftarrow$)
Consider input of size $n$. By Cook-Levin theorem, there is a $\poly(n)$ size boolean formula $\phi_n$ such that the size $n$ input is a yes instance iff evaluating the input plus the advice $a_n$ on $\phi_n$ is 1. Thus, by hardwiring the advice $a_n$ and transforming $\phi_n$ into a $\poly(n)$ size circuit $C_n$, all input of size $n$ can be solved by $C_n$. Namely, $L$ is decided by $\{C_i\}_{i\in\mathbb{N}}$.
$\P\in\Ppoly$
Let $L\in\P$. Consider input of size $n$. By Cook-Levin theorem, there is a $\poly(n)$ size boolean formula $\phi_n$ such that the size $n$ input is a yes instance iff the evaluation on $\phi_n$ is 1. Thus, by transforming $\phi_n$ into a $\poly(n)$ size circuit $C_n$, all input of size $n$ can be solved by $C_n$. Namely, $L$ is decided by $\{C_i\}_{i\in\mathbb{N}}$.
We can interpret this theorem as nonuniform computation model can simulate deterministic uniform computation model.
$\BPP\in\Ppoly$
Let $L\in\BPP$. Consider input of size $n$. By Cool-Levin theorem, there’s a $\poly(n)$ size boolean circuit $A(\cdot,\cdot)$ such that on input $x\in\{0,1\}^n$, we have:
- If $x\in L$, $\mathbb{P}_{r\leftarrow\{0,1\}^m}[A(x,r)=0]\leq1/3$.
- If $x\notin L$, $\mathbb{P}_{r\leftarrow\{0,1\}^m}[A(x,r)=1]\leq1/3$.
By repeating $A$ polynomial times, we get $\poly(n)$ size $A’(\cdot,\cdot)$ such that
$x\in\{0,1\}^n$, we have:
- If $x\in L$, $\mathbb{P}_{r\leftarrow\{0,1\}^m}[A’(x,r)=0]\leq2^{-2n}$.
- If $x\notin L$, $\mathbb{P}_{r\leftarrow\{0,1\}^m}[A’(x,r)=1]\leq2^{-2n}$.
Namely, $\mathbb{P}_{r\leftarrow\{0,1\}^m}[\exists x\in\{0,1\}^n,\ A(x,r)\neq\mathbf{1}_{x\in L}]\leq 2^n\cdot2^{-2n}$<1. Thus, we know that there exists $r^* \in\{0,1\}^m$ such that for any $x\in\{0,1\}^n$, $A’(x,r^* )=\mathbf{1}_{x\in L}$. Let $C_n = A’(\cdot,r^* )$, we have a poly-size circuit family $\{C_i\}_{i\in\mathbb{N}}$ that solves $L$.
We can interpret this theorem as nonuniform computation model can simulate probabilistic uniform computation model.
From the theorem about $\P\in\Ppoly$, we see how circuit family captures polynomial-time Turing machine. Now, let’s see the other direction. That is, under what condition would circuit family being captured by Turing machine.
Here, we introduce four results:
- $\P$ is equivalent to $\P$-uniform circuit.
- $\P$ is equivalent to logspace-uniform circuit.
- $\PH$ is equivalent to DC-uniform constant depth circuit.
- $\EXP$ is equivalent to DC-uniform circuit.
We say a circuit family $\{C_i\}_{i\in\mathbb{N}}$ is $\P$-uniform if there’s a polynomial time Turing machine such that for any $n\in\mathbb{N}$, on input $1^n$, the output of the Turing machine is the description of $C_n$.
We have an immediate result from the above definition.
A language $L$ is in $\P$ iff $L$ has a $\P$-uniform circuit family.
For complexity class $\P$, the notion of $\P$-uniform is a bit too powerful since we give the Turing machine the same power as $\P$. Another way to define the uniformness of circuit family is through restricting the Turing machine to work in logspace.
We say a circuit family $\{C_i\}_{i\in\mathbb{N}}$ is logspace-uniform if there’s a logspace Turing machine such that for any $n\in\mathbb{N}$, on input $1^n$, the output of the Turing machine is the description of $C_n$.
Clearly that if $\{C_i\}_{i\in\mathbb{N}}$ is logspace-uniform then it is also $\P$-uniform while the other direction might not be as trivial. The following theorem tells us that it is the case.
A language $L$ is in $\P$ iff $L$ has a logspace-uniform circuit family.
We say a circuit family $\{C_i\}_{i\in\mathbb{N}}$ is Directed Connected uniform (DC-uniform) if there’s a polynomial time Turing machine such that for any $n,i\in\mathbb{N}$, on input $\langle n,i\rangle$, the Turing machine outputs the $i$th bit of $C_n$.
A language $L$ is in $\PH$ iff $L$ has a DC-uniform circuit family with:
- AND, OR, NOT gates with unbounded fan-in,
- constant depth and $2^{n^c}$ size for some constant $c$, and
- all the NOT gates are in the input layer.
- ($\Leftarrow$) Let $C$ be a circuit family having the above properties and assume the depth of the circuits is bounded by constant $k$. Without lost of generality, assume the AND and OR gates are alternate. Note that these properties can be achieved by increasing constant size. Let’s design a polynomial time alternating Turing machine with $k$ alternations as follows.
- On input $x$, design a sub-routine: $Check_x(i)$, where $i$ the index of the gate in the circuit.
- $Check_x(i)$ works as follows:
- If $i$ is the input gate, then return the corresponding bit.
- If $i$ is an AND gate, then use an universal quantifier to query $Check_x(i’)$ where $i’$ has a wire to $i$. Note that we need to compute $i$ in poly-time.
- If $i$ is an OR gate, then use an existential quantifier to query $Check_x(i’)$ where $i’$ has a wire to $i$.
3. Output $Check_x(i^* )$ where $i^* $ is the output gate.
One can see that as long as the computation of the neighbors of $i$ can be done in poly-time, the above algorithm is in $\Sigma_k$ thus in $\PH$.
To find the neighbors of a gate in poly-time, first observe that the gates in the circuit can be encoded with $O(n^c)$ bits since the size of the circuit is $2^{O(n^c)}$. From a proper encoding, the Turing machine can find the position encodes the neighbor of $i$ in constant time and read out the index in $O(n^c)$ time. Thus, the whole process is in poly-time.
- ($\Rightarrow$) Let $L\in\PH$, there’s a ATM with $k$ alternations that decides $L$ in $O(n^c)$ time where $k$ and $c$ are constant. Think of the computation of the ATM in the configuration graph view. The computation in each node can be written as a size $O(2^{n^c})$ CNF. Also, the universal quantifier can be replaced with AND gate while the existential quantifier can be replaced with OR gate. The resulting circuit will be a constant dpeth-$2k$ size $O(2^{n^c})$ circuit.
A language $L$ is in $\EXP$ iff $L$ has a DC-uniform circuit family with:
- AND, OR, NOT gates with unbounded fan-in,
- arbitrary depth and $2^{n^c}$ size for some constant $c$, and
- all the NOT gates are in the input layer.
We prove the theorem by showing the class of DC-uniform circuit families above is equivalent to $\APSPACE$
- ($\Leftarrow$) Apply the same reduction in the proof of the above theorem. One can see that the required space is $O(n^c)$.
- ($\Rightarrow$) Apply the same reduction in the proof of the above theorem. As the space
$\P$-completeness
In the previous topics, we defined $\NP$-completeness to capture the hardest problems in $\NP$. Similarly, we would like to define $\P$-completeness for the hardest problems in $\P$. However, what do we mean by the hardest problems in $\P$? Since every problems in $\P$ can be solved in polynomial time, one can see that the original polynomial-time reduction doesn’t work anymore since every problems in $\P$ can be reduced to each others in polynomial-time.
It turns out that logspace reduction is a nice notion to capture the hardest problems in $\P$. We define the $\P$-completeness as follows.
A language $L$ is $\P$-complete if $L\in\P$ and every problems in $\P$ can be logspace reduced to $L$.
One of the reason why we define $\P$-completeness using logspace reduction is that it is parallelizable.
Brief introduction to circuit lower bound
We have seen some connections between uniform computation model and circuit family. Specifically, we saw $\P\in\Ppoly$ and $\P$ is even equivalent to a weaker version of $\Ppoly$ ($\P$-uniform and logspace-uniform). However, surprisingly, for larger uniform complexity classes, we have little knowledge about their relations to $\Ppoly$. Intuitively, we believe $\NP\notin\Ppoly$, however, we even cannot rule out $\NEXP\in\Ppoly$!
In this section, we are going to see some of the results trying to provide circuit lower bounds, \ie showing that certain uniform complexity class does not lie in certain circuit complexity class. As circuit has more structure than black-box, we somehow believe that this could be a potential approach to prove something like $\P\neq\NP$.
Karp-Lipton and Meyer
Karp-Lipton theorem is one of the fundamental theorem in circuit complexity. The proof of it is simple, however, the importance of this theorem is how interpret it. Here, we first state the theorem and provide a simple proof. Then, we will discuss its implication and another related theorem: Meyer theorem.
If $\NP\in\Ppoly$, then $\PH=\Sigma_2$.
Suppose $\NP\in\Ppoly$, we are going to show that polynomial hierarchy collapses to the second level. From out previous lecture, we know that it suffices to show $\Pi_2=\Sigma_2$.
For any $L\in\Pi_2$, there’s a polynomial size boolean formula $\phi(\cdot,\cdot,\cdot)$ such that for any $x\in\{0,1\}^n$, $x\in L$ iff $\forall y \exists z \phi(x,y,z)=1$. Let $m=\poly(n)$ denote the size of $\phi$. As $\SAT\in\Ppoly$, there exists a circuit $C_m$ such that for any $x,y$, $C_m(x,y)=1$ iff $\exists z$ such that $\phi(x,y,z)=1$. Namely,
\begin{equation}
x\in L\Leftrightarrow \forall y \exists z \phi(x,y,z)=1 \Leftrightarrow \exists C_m \forall y C_m(x,y)=1.
\end{equation}
As everything is polynomial in $n$, $L\in\Sigma_2$ and $\PH=\Sigma_2$.
If $\EXP\in\Ppoly$, then $\EXP=\Sigma_2$.
The critical idea in the proof of Meyer theorem is the concept of transcript. For a language $L\in\EXP$, for any input $x\in\{0,1\}^n$, its transcript is the snapshots of the execution of the Turing machine. Concretely, suppose the Turing machine runs in $n^c$ time, the transcript of $x$ is a function $T_x:[2^{p(n)}]\times[2^{p(n)}]\rightarrow\Gamma$, where $\Gamma$ is the alphabet set and $p$ is a polynomial. Note that the two indices of $T_x$ are polynomial in $n$ and $T_x$ itself is exponential in $n$.
Now, we can formulate a new language that verify the correctness of transcript.
\begin{equation}
L’ = \{(x,i,t,z):\ T_x(i,t)=z \}.
\end{equation}
Since $i,t$ are polynomial in $n$ and $T_x$ can be generated in exponential time, $L’\in\EXP$. As a result, by the assumption, $L’\in\Ppoly$. Namely, there exists a circuit $C$ of size $\poly(n)$ such that for any $x\in\{0,1\}^n$, $i,t\in[2^{p(n)}]$, and $z\in\Gamma$,
\begin{equation}
(x,i,t,z)\in L’\Leftrightarrow C(x,i,t,z)=1.
\end{equation}
Furthermore, there exists a circuit $C’$ of size $\poly(n)$ such that for any $x\in\{0,1\}^n$, $i,t\in[2^{p(n)}]$,
\begin{equation}
(x,i,t,z)\in L’\Leftrightarrow C’(x,i,t)=z.
\end{equation}
To make sure $x\in L$, we need to check that for all $i,t\in[2^{p(n)}]$, $T_x(i,t)$ is correct. Now, from our previous discussion, we know that there exists a poly-size circuit $C’$ that can efficiently output the content on the transcript so that we can verify with a PPT Turing machine. The problem becomes:
\begin{equation}
x\in L\Leftrightarrow \exists C\forall i,t\in[2^{p(n)}] A(C’(x,i,t))=1,
\end{equation}
where $A$ is a PPT Turing machine that locally verify the correctness of $C’$. Namely, $L\in\Sigma_2$.
The following is the flow of the proof.
graph TD
A(L in EXP)-->B(L' in EXP)
B-->D(L' in P/poly)
C(EXP in P/poly)-->D
D--exists C to verify all input in poly-time-->E(L in \Sigma_2)
Shannon’s counting
For $n\in\mathbb{N}$ large enough, there exists $f:\{0,1\}^n\rightarrow\{0,1\}$ such that $f$ cannot be computed by circuit of size $2^n/(10n)$.
Let $S=2^n/(10n)$. Let’s count the number of $n$-bit boolean function that can be computed with size $S$ circuit. Indexing each node in the circuit with $\log S$ bits and recording its neighbor and gate type with constant bits, we can represent a size $S$ circuit with at most $4S\log S$ bits. Namely, there are at most $2^{4S\log S}=o(2^{2^n})$ $n$-bit boolean function can be computed with size $S$ circuit.
Here are some remarks:
- Here the proof involves the so called counting argument (Sometimes being phrased in probabilistic method language). It is widely used to show the existence of certain object. In my subfield of TCS, the goal is to achieve the construction hinted by this information-theoretic argument.
- From the proof, we can see that actually the majority of the $n$-bit boolean functions do not have circuit of sub-exponential size.
- Current best circuit lower bound for $\NP$ is $(5-o(1))n$.
- $\PH$ has better better circuit lower bound: $\forall k>0$, there exists $L\in\PH$ such that $L$ cannot be computed by circuit of size $O(n^k)$.
- For more restricted circuit models, we have better lower bound using sophisticated techniques introduced later.
Three important historical works
- $Parity\notin AC[0]$.
- Razborov monotone circuit lower bound.
- Natural proof.
Latest $\NEXP\not\subseteq ACC$ result.