$
\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}
$
On the Algorithmic Power of Spiking Neural Networks
15 Jan 2019
2019的第一趟旅行，來到了四季如春的San Diego，這三年來在三個不同的季節拜訪這裡，每次的天氣都是一樣的舒適，難怪大家都說San Diego是個適合養老的地方。不過硬要說個讓我不會想要長久待在這邊的原因，大概就是這邊的植物真的常常讓我看的不順眼吧，這些沙漠植物對我來說真的有點太沒氣質了！？
這次的目的是來ITCS 2019報告最近的一篇和中研院鍾楷閔老師還有呂及人老師合作的paper：「On the Algorithmic Power of Spiking Neural Netowrks」，這是我研究生涯中第一個開始的project，也是做最久的一個。從初期毫無方向，不知道該怎麼開頭，到開始有點小結果，但是卻遲遲證明不出最理想的大定理。在申請Ph.D.的時候還常常自怨自艾，為什麼要想不開去做這種吃力不討好的題目。到了現在，終於在去年暑假把塵封已久的問題解決掉了，文章也順利地被ITCS接受，如今來到San Diego開會，在準備的過程中，更是讓我重新檢視了這個work的定位，甚至是說讓我重新愛上了這個work。
緣起
難得這次不是搭紅眼班機從西岸飛回Boston，趁著Alaska airline沒有提供電影設施，就來寫寫這個研究的心路歷程吧！
時間要先拉回升大四的那年暑假，在經過了軟體工程的專題之後，我終於下定決心要來做理論研究，於是到了中研院找鍾楷閔老師(簡稱KM)做暑期實習生。KM的研究興趣是(量子)密碼學，然而在那時我年輕不懂事，在基礎知識不足的情況下，還不太能appreciate這個方向的研究，也因此在讀了幾篇paper還有上完了暑期的密碼學課程後，還是遲遲沒有找到一個感興趣的研究方向。在暑假的尾聲，我決定要繼續待在KM這邊，而KM也跟我講了幾個他感興趣的研究方向，如果我的記憶正確的話，還記得一個是multiparty computation的問題，一個是circuits lower bounds，一個則是今天的主角spiking neural networks。
當時的我大概是覺得前兩個研究方向KM似乎也沒有什麼具體的想法，而且又是非常深的坑，即使我很感興趣(turns out我現在很著迷於circuits lower bounds)，也不見得做得動，可能淪落於做些survey，這樣我自己offline做不就可以了。而如果是做spiking neural networks相關的研究，這在當時的理論CS圈子內，幾乎沒有什麼人在研究。雖然KM也不是這邊的專家，但是也許透過這樣的過程，能夠讓我學習一個厲害的研究人員是怎麼樣做自己完全不懂的方向吧？於是就抱持這樣的想法，開始了這趟耗時超過三年的旅程。
背景
脈衝神經網路(Spiking neural networks, SNNs)是指neuroscientists在研究真正生物的神經網路(例如我們的大腦)時所用的數學模型，由於生物的神經網路實在太複雜了，於是neuroscientists會抽象出許多不同的SNNs模型，來幫助他們了解實際的生物現象。
而對於computer scientists來說，有一群人他們的目標是想要設計出類似大腦神經元的晶片，然後想要能夠比傳統電腦在某些常見的計算問題上，能夠有更快更好的效率。因此他們試圖在SNNs的模型框架之下，設計演算法，想要解決實際的問題。然而在現階段來說，這些都是完全沒有理論支持的。具體來說，沒有理論可以說明為什麼使用SNNs模型可以在這些計算問題上有好的表現，而且即使SNNs在一些模擬中能夠有好的表現，大家也不知道SNNs是怎麼做到的，然後在什麼樣的情況下有可能會表現得很差。
這樣缺乏理論支持的情況，主要是因為SNNs是個看似簡單，但是卻有著非常不連續行為的數學模型。具體來說，讓我們看看一個常見的SNN模型，叫做 integrate-and-fire SNN。在這個模型中，每個神經元(neuron)會有個電位(membrane potential)隨著時間變化。有兩種因子會影響電位的改變，第一種是個固定的外部充電，可以想成是這群神經元以外的東西造成的影響，而為了分析方便，通常我們會先假設這個充電的速率是個穩定不改變的值。第二種影響電位的因子是脈衝(spike)造成的影響。首先在integrate-and-fire SNN中，一個神經元會在他的電位超過閥值的時候，發射一個脈衝(fires a spike)，然後這個脈衝會傳輸到其他的神經元，然後影響它們的電位。這個影響的程度，是根據神經元之間的突觸強度(synapse)來決定的。而在數學模型中，突觸的強度則是簡單的被用一個數字表示。如果現在有$n$個神經元，那麼最多就會有$n^2$個突觸(包括神經元自己跟自己的)，而這些數字可以被一個$n\times n$的矩陣記錄起來。
更多的背景介紹，歡迎參考我們的paper或是投影片！
研究初期
這個研究最一開始的起點是一篇神經網路學家的paper(Barret-Denéve-Machens NIPS 2013)。對於neuroscientists來說，透過深入了解SNN模型的一些基本性質，可以幫助他們更認識生物的神經網路。而在這一篇paper中，他們在探討integrate-and-fire SNN的平均脈衝個數(firing rate)。他們觀察到平均脈衝個數在實驗中會收斂到一個最佳化問題的解。具體來說，當外部充電是$\mathbf{I}$和突觸矩陣是$C$的時候，平均脈衝個數在實驗中會很快的收斂到下面這個非負最小平方問題的解答：
\begin{equation}
\min_{\bx\in\bbR^n,\ \bx\geq0}\|C\bx-\bfI\|_ {2}.
\end{equation}
對神經網路學家來說，這個觀察可以讓他們使用這個最佳化問題來幫助了解SNN的平均脈衝個數。不過如果換另一個角度來看，這個觀察也可以被理解成integrate-and-fire SNN使用著平均脈衝個數去解了一個非負最小平方問題，也就是說我們可以把integrate-and-fire SNN看成一個非負最小平方問題的演算法！不過在這篇arret-Denéve-Machens的paper中，沒有任何的理論分析還有解釋。因此身為理論電腦科學家(當時我可能只是理論電腦科學學徒就是了…)，我們的目標便是要對這個關於平均脈衝個數和非負最小平方問題的觀察提出嚴謹的理論根據。
不過什麼叫做「提出嚴謹的理論根據」呢？精確來說的話，是指能夠(i)找到一些關於$C$還有$\mathbf{I}$的條件，然後(ii)證明在讓SNN跑了$t$秒之後，平均脈衝速率會和非負最小平方問題的解有多接近。在專業的術語上，這稱之為做出一個 收斂速率(convergence rate) 的分析。
在經過幾個月的學習和研究之後，我們很快的就針對一個特別的條件，證明出平均脈衝個數會很快的收斂到最小平方問題的解。雖然這個證明只用到了很基礎的線性代數，不過令當時的我雀躍不已。但是我也知道這只是剛開始而已，畢竟我們考慮的這個條件有點太過於限制，而且我們只會證明平均脈衝個數會收斂到最小平方問題的解，而不是 非負 最小平方問題的解。
有了關鍵的發現，卻證明不出來關鍵的定理
當我們在一個特殊條件下證明出想要的收斂結果後，一時之間沒有什麼頭緒該把這個條件拿掉。不過倒是很快有個很有趣的發現：當最小平方問題有不只一個解答的時候(當矩陣$C$是overdetermined的時候會發生)，平均脈衝速率在實驗上似乎都會收斂到比較稀疏(sparse)的解答。更精確一點來說，我們強烈猜測平均脈衝速率會收斂到最小平方問題的最小$\ell_1$ norm解。
\begin{equation}
\min_{\bx\in\bbR^n,\ A\bx=\bb}\|\bx\|_ 1.
\end{equation}
這個最佳化問題又被稱為 最小$\ell_1$問題。
這對當時的我們來說是個非常興奮的發現，在系統性的調查相關的研究後，我們發現沒有人對於integrate-and-fire SNN提出類似的觀察，更不用說理論的證明了。
除了在實驗上的這個觀察之外，另外一個更振奮人心的發現是我們在integrate-and-fire SNN的數學模型中，找到了一個很有趣的變量，這個變量乍看之下非常自然的會收斂到最小$\ell_1$問題的 對偶問題 的解！具體來說，這個變量的行為可以被下面這個數學式描述：
\begin{equation}
\bv(t+1) = \bv(t) - A\bs(t)+\bb.
\end{equation}
而最小$\ell_1$問題的對偶問題則是如下。
\begin{equation}
\max_{\bv\in\bbR^n,\ \|A^\top\bv\|_ \infty\leq1}\bb^\top\bv.
\end{equation}
根據integrate-and-fire SNN中神經元發射脈衝的規則，在直覺上可以把\bv(t)式子中的$\bb$想成是對偶問題的梯度方向(gradient)，然後把脈衝的影響$-A\bs(t)$想成是幫助$\bv(t)$回到對偶問題的合適空間(feasible region)。
然而上面描述的當時都還處於觀察臆測階段，但是這個和對偶問題的關聯實在是太乾淨漂亮了，讓我們覺得這應該就要是個對的方式來做integrate-and-fire SNN的理論分析了。於是我開始著手研究這些相關的最佳化問題，然後試著用各種技巧來突破，可是卻不斷地失敗。還記得當初有一段期間，每天一大早我就會帶著新想到的方法跑到KM的辦公室找他討論，然後過了一陣子後就找到一些反例。回家思考半天之後，覺得解決掉這個反例了，隔天要興沖沖的跑去討論，然後又再度帶著失望離開。
於是我們就這樣在一個「有了關鍵的發現，卻證明不出來關鍵的定理」的階段卡了整整一年，直到我離開台灣去Harvard讀Ph.D.之前，我們依然不知道怎麼嚴謹的證明我們的這個觀察。
進入寫作階段，但是卻不斷地被reject
來到Harvard之後，我們暫時的放棄嘗試去證明這個有趣的發現，轉而投入先把已經有的結果和觀察寫出來，然後試著投稿到理論的會議，看看有沒有機會讓這個問題被更多人看到，然後說不定就會有些想法可以來做做看了。
然而迎接我們的卻是整整一年滿滿的rejection，由於我們不會證明理想中的大定理，已經有的結果又限制太多，再加上我們對於這種跨領域的題目掌握度還不夠好，在前面嘗試的幾個版本中，常常讓讀者誤解我們的研究方法，有時候甚至可以說是我們自己都還沒有很清楚該怎麼樣定位這一個研究。
這段期間大概是這個研究最低潮的階段了吧，我們一度還考慮乾脆就送到一個排名比較後面的會議就好了。要不是我在Harvard有些其他的研究結果，我真的會時常懷疑自己做研究的能力。很幸運的是，兩位老師在這個研究上給我很大的鼓勵和自由度，所以最後沒有放棄，也因此才有了最後的轉捩點。
下定決心的全力一搏
在2018年的暑假，我在CCC 2018(也是在San Diego舉辦的！)報告了一篇關於multivariate polynomials factorization的研究，然後順路去了LA參加STOC 2018。在那邊的其中一個午餐，和一個UC Berekeley做圖論算法相關的學生，聊到了這個SNN的研究。原本想說跟他講講說不定他會有些有趣的技巧，最後雖然沒有如願得到有用的feedback，但是卻莫名的讓我想要重新來證明看看，於是在暑假到處跑來跑去之餘，腦中開始構思證明的一些新思路。
開學前的最後幾個禮拜，我來到了Simons institute去參加lower bounds的workshops。眼看ITCS的死線將近，我開始在通勤的一些閒雜時間開始重新思考如何擊破這個證明。當初我們其實已經有個還蠻完整的計畫，只是一直找不到合適的“potential function”。
通常在證明一個演算法可以解一個最佳化問題的時候，常見的做法是找出一個”potential function”，然後證明(i)這個演算法的error會被potential function控制住(ii)這個potential function會持續的遞減。如果能夠同時達到這兩件事式，那麼就可以證明這個演算法可以慢慢逼近最佳化問題的最優解。
然而在這個問題中，我們嘗試過各種很直接的potential function，但是每一個都會在一些特殊的情況下違法了兩個條件的其中一個。真的是絞盡了腦汁，都還是沒有一次成功過。於是在這次的嘗試中，我決定採取不一樣的方式。我先從一個很早期嘗試過但是失敗的potential function作為起點，然後一旦遇到了反例，我就在定義另外一個potential function使得他在這個反例中會正常的運作。然而這個potential function還會有其他的反例，不過沒關係，我就在定義另外一個potential function。如此依樣畫葫蘆的弄下去，最終我可以定義出一連串的potential functions，使得(i)SNN firing rate的error會被這些potential function的“和”給控制住(ii)在SNN的每一個步驟中，至少會有一個potential function會嚴格的遞減。如此一來，這些potential function的“和”就可以同時達成一個potential function該符合的兩個條件了！
收尾
再把一切細節搞定之後，花了一個週末和幾個下午，好好的把paper改寫好，順利地趕上ITCS的死線，最終也順利地被接受。在收到通知信的當下，心中除了喜悅和成就感之外，更是在研究上多了許多自信。
在開會前的一個月，趁著放寒假，也開始慢慢的構思演講的結構。這次ITCS的演講長度只有12分鐘，也就是說幾乎不太可能把所有想要講的東西清楚地講完。經過一個多禮拜的醞釀，我做出了第一個版本的投影片，然後試著報告一次給KM聽。結果因為要省時間，加上又想要強調一些技術細節，犧牲了big picture，反而更沒辦法讓聽眾抓到這個研究的貢獻。於是又花了幾天做了第二個版本，試圖交代多一點的背景知識還有大方向的想法，結果變成改太多，整個報告變得太過天馬行空，不夠具體。就這樣不斷地一來一回，最後終於在報告前三天抓到了一個不錯的平衡。然後開始不斷的練習，終於可以穩定的把時間掌控在11到12分鐘。
時間一晃眼就來到開會報告的日子了，雖然運氣很不好遇到了San Diego的下雨天，不過還是順利完成報告，也獲到了不少人的稱讚。收到稱讚固然很開心，但是最讓我開心的還是莫過於總算好好的完成了一個從零開始的研究，一路上從定義出問題、尋找相關資料、和其他人交流討論、卡關在困難的技術問題，到最後終於解決難題，然後透過寫paper還有給演講把整個研究定位清楚，並且讓別人輕鬆的搞懂我們在做些什麼。
回想當初還沒出國念Ph.D.的時候，總是覺得自己都沒有研究結果，然後唯一一個在進行的研究又是個這麼不是標準TCS style的問題，時常會懷疑這個研究的價值到底在哪裡。在經歷了三年多的起起伏伏，現在我終於可以很有自信將這個Spiking Neural Networks的研究介紹給朋友，告訴他們在想法上還有技術上我們做出的貢獻是什麼，對於其他相關領域的影響會是什麼。
不過話說回來，看看現在的自己，反而沒有像當初一樣挑戰這種長期的研究目標，而是把大部分時間花在一些比較技術性但是缺少原創性的問題。雖然也許比較有穩定一點的產出，不過Ph.D.這麼多的時間，還是該來做一些大的問題呀！期待接下來可以找到一個好的大方向，定下來做出一些比較有原創性的工作！