$ \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{\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{\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]{\lvert #1 \rvert} \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{\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{\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}} \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{\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{\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{\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} $
$ \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{\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{\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]{\lvert #1 \rvert} \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{\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{\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}} \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{\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{\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{\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

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.這麼多的時間,還是該來做一些大的問題呀!期待接下來可以找到一個好的大方向,定下來做出一些比較有原創性的工作!

2018 Lower Bounds Program at Simons Insitute

今年秋季Simons Institute的其中一個program是關於計算複雜度的下界問題,這恰巧是我最感興趣的方向。為了抓住夏天的尾巴,不顧開學即在眼前,我匆匆買了機票,到舒服的加州享受太平洋的涼風。

這個program橫跨一學期,包含了四個正式的workshops,還有無數的相關訪問學者以及他們帶來的reading groups和seminars,可以說是把地球上做相關領域一半的專家都吸引了過來。身為一個小小博士生,這正是個好好學習的機會呀!在拜訪的這一個月中,參加了兩個workshops(bootcamp還有boolean devices)還有和一些身邊的visitors交流學習,雖然並不是特別外向到處去認識大老們,不過還是有多多少少在一些互動中增加了不少新的知識還有直覺。最重要的是,在這個眾星雲集的地方,了解了不少最尖端的問題。

身為一個還很菜的研究者,我覺得在做研究中最困難的一步就是找出做得動又重要的問題。一個很常犯的錯誤往往是想一個太過於困難的問題,而前人已經有非常多失敗的原因解釋為什麼現階段的工具不夠用。這並不是說想困難的問題不好,而是說一個研究者要時時刻刻清楚的知道這個問題的定位,哪些方法一定不會成功,然後原因是什麼。一個好的研究題目就是在這些複雜的問題海中,找出既有希望有些突破,又能夠帶來一些後續的影響。

當然,說說總是很容易,這一個月下來聽了無數場的演講還有各種open problems,也說不準有哪些是值得深入研究思考的,大概也是到有人做出來了才會豁然開朗。不過趁著年輕不怕出醜,還是把握這個機會來想想看哪些問題是值得進一步研究下去的。以下整理一些我個人覺得重要或是有機會做得動的open directions,有些明顯是非常困難的long standing problems,不過也許是缺乏人們用力的去不斷想它,是個可以放在心上定期拿出來想想的東西。

Multilinear formula vs. Formula

Multilinear formula是一個arithmetic circuits中的特例,限制使用formula(每個gate的out-degree是1),然後每個gate計算的polynomial是multilinear的,也就是每個variable的degree不超過1。例如$x^2yz$不是multilinear但$xz$是。

在沒有multilinear限制時,一般的arithmetic circuit還有formula只有$\Omega(n\log n)$和$\Omega(n^2)$的lower bounds,不過到了multilinear formula時,使用partial derivative matrix的技巧,可以獲得exponential的lower bound。

這樣看似這個方向的問題已經結束了,畢竟我們還是沒有formula的exponential lower bound,看來multilinear把formula弱化太多了,不過事情沒有這麼單純。仔細去看看multilinear formula的lower bounds時,會發現到那些lower bound使用的polynomials,都是比較複雜的polynomials。例如permanent, determinant等,他們本身並沒有已知的polynomial-size的formula(最小的是可以被$O(\log^2n)$-depth的circuit計算)。也就是說,目前人們可以separate一般的circuit還有multilinear formula,但是formula還有multilinear formula之間的強弱關係是還沒有被完全解決的。

這樣有趣的點會是什麼呢?我個人的看法是這會是一個雙贏的局面:如果很意外的formula和multilinear formula的計算能力是差不多的(這大概沒有人相信,不過目前也沒有人可以排除這個情況),那麼我們將會馬上獲得formula的exponential lower bound,這將會是一個重大的突破。另一方面,如果可以把formula和multilinear formula分開,那某種程度是發現了formula的新強大計算能力,畢竟只有polynomial-size的formula可以計算multilinear formula需要exponential-size才做得到的事情。這樣的發現相信可以幫助我們更了解formula的能力,也許能有更多insight了解為什麼要證明$\omega(n^2)$的formula lower bound是這麼困難的事情。也就是因為這樣雙贏的局面,讓我認為這個問題是重要的。

而這個問題也是我覺得在近期內也許有希望能被解決的。我目前是沒有什麼具體的想法,所以這邊就只簡單整理一下兩個方向的state-of-the-art。

如果要證明formula和multilinear formula的計算能力是差不多的(再次強調,這個方向應該大部分人都覺得不可能),那麼基本上就是要把一個一般的formula轉成一個multilinear formula並且只有polynomial的size blowup。目前只有Ran Raz在一篇把formula lower bound和tensor rank lower bound扯在一起的文章中,把一般的formula轉成了set-multilinear formula,其中只允許有$\tilde{O}(\log n)$個variable sets(這邊不詳細定義set-multilinear,其實就是規定在同一個set中的variable只能有一個出現,請參考Raz的paper)。如果要證明formula和multilinear formula的計算能力是差不多的,那麼把Raz的$\tilde{O}(\log n)$變成$O(n)$就夠了,不過他的技巧很顯然沒辦法做到這樣。目前也沒有什麼跡象可以做的這樣,即使這個方向是對的,大概也需要蠻多的新想法。

另一個方向則是非常接近了。Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan最近證明了當我們限制formula和multilinear formula的深度是$o(\log n)$時,那麼就會有polynomial-size的formula和multilinear formula的separation。也就是說,如果把他們的$o(\log n)$變成$O(\log n)$就大功告成了。但是為什麼他們就這樣停在門口呢?這就要從他們使用的技術來看起。先說結論,他們的套路是沒辦法突破$o(\log n)$的,除非有些很新的想法。

Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan的做法有兩步:(i)用Ran Raz之前證明exponential multilinear formula lower bound的partial derivative matrix技術證明一個特別的polynomial(其實也沒有那麼特別,是$d$個$2\times 2$的iterative matrix multiplication)在深度$\Delta$的multilinear formula需要大小$exp(d^{1/\Delta})$。(ii)使用有名的GKKS深度節約(depth reduction)技術,證明這個polynomial可以有大小$exp(d^{1/2\Delta})$深度$\Delta$的formula。大家可以把$d$設成$\log^{2\Delta} n$那麼就會有個exponential的separation了。然而,也不難發現$\Delta$必須要比$O(\frac{\log n}{\log\log n})$小不然GKKS得到的formula size也超過polynomial了。而至於為什麼我說他們大概無法突破深度$o(\log n)$的限制,是因為這已經是GKKS能夠給出最好的upper bound了。如果想用同一個polynomial繼續弄下去,必然會需要更厲害的技術,也就等同於要開發出formula更厲害的計算能力。

總結一下這個問題,我個人覺得兩個方向都直得思考一下,畢竟這個問題會卡住,似乎代表著我們對於formula的了解不夠(upper和lower bounds都是),而無論哪個方向結果都會是有趣的。

Different proof for AC0 lower bounds?

$\AC{0}$是一個經典的circuit class,包含了所有(polynomial-size的)contant depth且unbounded fan-in的circuits。$\AC{0]}$基本上是最所有non-trivial的circuit classes中最簡單的一個,早在三十年前就已經有exponential的lower bound存在。事實上,這個lower bound:$PARITY\notin\AC{0}$是目前已知對於$\AC{0}$最好的一個lower bound。具體來說,對於深度$d\geq0$的$\AC{0}$ circuit來說,需要$2^{\Omega(n^{1/(d-1)})}$個gates來計算PARITY。

當深度$d=2$時,PARITY的$\AC{0}$ lower bound是$2^{\Omega(n)}$,這又被稱為strong exponential lower bound。然而當$d>2$的時候,這個lower bound就變得不夠強了,例如當$d=3$,只有$2^{\Omega(\sqrt{n})}$。同時對於PARITY來說,這個lower bound是緊的,也就是說對於深度$d>2$的$\AC{0}$來說,無法用PARITY獲得strong exponential lower bound。

更悲慘的是,目前已知證明$\AC{0}$ lower bounds的技術很侷限於兩種:(1)隨機限縮法(random restriction)還有(2)多項式逼近法(polynomial approximation)。基本上PARITY是這兩種方法可以獲得最強lower bound的候選人了,雖然我們看似很了解$\AC{0}$,但是我們真的那麼了解嗎?有沒有可能找出新的證明$\AC{0}$ lower bound的方式?此外,有沒有除了PARITY以外的$\AC{0}$strong lower bound候選人?

目前我也是完全沒有什麼具體想法,一個潛在想要了解的方向是隨機限縮法的極限在哪。畢竟PARITY的lower bound是用最基本的一個隨機限縮法就做到了,如果使用一些比較花俏的限縮方式,Benjamin Rossman有個$k$-clique的exponential lower bound。有沒有辦法用比較複雜一點的隨機限縮法得到$\AC{0}$的strong exponential lower bound?或是能夠說明隨機限縮法做不到?

Updates: 這幾天又多看了一些書,學到了一些針對三層$\AC{0}$的相關結果。如上面所說目前三層$\AC{0}$最好的lower bound是$2^{\Omega(\sqrt{n})}$,Valiant多年前的一個結果說了如果可以把這個lower bound改進到$2^{\Omega(n/\log\log n)}$,那麼就會有個$O(\log n)$深度的$\omega(n)$ circuit lower bound。這個lower bound是證明$\NP\not\subseteq\Ppoly$的必經之路,但是還離目前大家會證的lower bound差很遠。

而三層$\AC{0}$的lower bound也不是完全沒有潛在的方法,一個古早的做法是考慮圖的複雜度(graph complexity)。例如如果可以證明對於所有$D$,每個$D$-regular的$K_{2,2}$-free圖,都需要$D^{\Omega(1)}$個independent set才能覆蓋所有的邊,那麼就可以得到$2^{\Omega(n)}$的三層$\AC{0}$ lower bound。

Depth-2 threshold circuits lower bounds?

目前boolean circuit lower bound的最前戰線被拉到了深度2的threshold circuits。在這邊threshold circuit是指所有的gate都是長得像下面這個樣子: \begin{equation} g(x) = sgn(\sum_{i\in[n]}w_i\cdot x_i-t) \end{equation} 其中$sgn(X)$是$X$的正負號,然後$w_i$還有$t$是一些整數。當$w_i$還有$t$的大小是polynomial in $n$,那麼我們稱$g$為一個majority gate,不是的話稱為threshold gate

To be continued…

CCC 2018

Few weeks ago, I attended the 33rd Computational Complexity Conference (CCC 2018) at UCSD. It was my first time going to CCC and I really enjoyed it a lot. As some of my friends told me before, since CCC is quite small and focused (in complexity), sometimes one can find it more useful and helpful. Personally I even like CCC 2018 more than FOCS 2017. The following are some papers that I found interesting to me during the conference. I decided to carefully study these papers and write some thoughts about them after the conference, however, it took much more time than I expected to finish this task.

The Power of Natural Properties as Oracles

Author(s): Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich.

The goal of this paper is two-fold. Firstly they want to investigate how powerful a natural property is following the learning with natural proof work by (Carmosino, Impagliazzo, Kabanets, & Kolokolova, 2016). On the other hand, they provide envidence that the minimum circuit size problem, i.e., $\MCSP$, is as hard as $\NP$.

Here, we list some of their results in the following.

  • $\ZPEXP^{\MCSP}\not\subseteq\Ppoly$ improving the previous $\ZPEXP^{\NP}\not\subseteq\Ppoly$.
  • $\ZPP^{\MCSP}/1\not\subseteq\SIZE[n^k]$ for all $k\in\N$.
  • Suppose indistinguishable ofuscation exists, then $\MCSP\in\ZPP$ if and only if $\NP=\ZPP$.
  • Replace the $\NP$ oracle in many complexity relations with $\MCSP$ oracle.

Collapse theorem

Let $\Gamma\in\{\PaP,\ShP,\PSPACE,\EXP,\NEXP,\EXP^{\NP}\}$. If $\Gamma\subseteq\Ppoly$, then $\Gamma\subseteq\ZPP^{\MCSP}$.

To interpret this theorem, one have to compare with the previous results. Prior to this work, $\Gamma$ would only collapses to $\MA$ (see this note) which lies in $\ZPP^{\NP}$. The above theorem in some sense indicates the power of $\MCSP$ being an oracle is as powerful as $\SAT$.

Circuit lower bounds

$\ZPP^{\MCSP}/1\not\subseteq\SIZE[n^k]$ for all $k\in\N$.

Note that this is an analogy to the $\MA/1\not\subseteq\SIZE[n^k]$ due to Santhanam (Santhanam, 2009) (see this note). As we mentioned previously, $\MA\subseteq\ZPP^{\NP}$ and thus $\ZPP^{\MCSP}$ can be thought of as a $\MCSP$ analogy for $\MA$.

Key technique

The following is a kel lemma extracted from (Carmosino, Impagliazzo, Kabanets, & Kolokolova, 2016) using natural proof (see this note) to learn boolean function.

Let $\mathcal{R}$ be a strongly useful natural proof and let $L$ be a downward self-reducible and self-correctable language. Then, there exists a randomized algorithm with oracle queries to $\mathcal{R}$ such that on input $x$, output $L(x)$ correctly with probability at least $1-1/\poly(n)$ in time $\poly(\card{x},\text{size}(L))$.

An immediate corollary would be a conditional collapse of $\PSPACE$ to $\BPP^{\MCSP}$ since there is a downward self-reducible and self-correctable language in $\PSPACE$ and $\MCSP$ is a strongly useful natural proof.

To move from $\BPP^{\MCSP}$ to $\ZPP^{\MCSP}$, we need one more lemma as follows.

Let $\mathcal{R}$ be a strongly useful natural property. Then, $\BPP\subseteq\ZPP^{\mathcal{R}}$. Moreover, if $\mathcal{R}\in\Ppoly$, then $\BPP^{\mathcal{R}}=\ZPP^{\mathcal{R}}$.

Some thoughts

To some extent, the techniques used in this paper are not that surprising after the CIKK paper, however, the high-level message is informative. I feel that these results all highly rely on the self-reducibility of a $\PSPACE$-complete language. Is that possible to go beyond this? Say having similar results for lower complexity classes that do not have a self-reducible language?

Pseudorandom Generators from Polarizing Random Walks

Author(s): Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett.

This work gives a new framework of constructing pseudo random generator (PRG) by using fractional PRG. They construct PRG for functions with low sensitivity with better seed length as well as PRGs for other family of well-studied functions. The key constrution is a fractional PRG for function with exponentially decaying $\ell_1$ tail. In the following, we will first define some notations and present some of their results.

Here, we think of PRG as a random variable $X$ distributes in ${-1,1}^n$ defined as $X=G(U_r)$ where $G:{-1,1}^r\rightarrow{-1,1}^n$ is the generator function, $U_r$ is uniformly distributed over ${-1,1}^r$, and $r$ is the seed length. We say $X$ $\epsilon$-fools a function $f:{-1,1}^n\rightarrow{-1,1}$ if \begin{equation} \left|\E[f(X)]-\E[f(U_n)]\right|\leq\epsilon. \end{equation} The goal is to minimize the seed length $r$. Note that there are other ways to define PRG and they are basically equivalent.

Fractional PRG

A fractional PRG prosed in this paper is a random variable $X$ distributes in $[-1,1]^n$ instead of ${-1,1}^n$ while having the same $\epsilon$-fool property. However, to avoid triviality ($X$ always being $0^n$), we say $X$ is $p$-noticeable for some $p>0$ if $\E[X^2]\geq p^2$.

The paper mentions that a $p$-noticeable fractional PRG that fools function with exponentially decaying $\ell_1$ Fourier tail can be constructed with bounded-wise independent random variables. Concretely, they have the following lemma.

For any $a,b>0$ define $\mathcal{F}_{a,b}^n=\{f\ |\ \sum_{S\subseteq[n]:|S|=k}\card{\hat{f}(S)}\leq a\cdot b^k\}$ be the family of functions with exponentially decaying $\ell_1$ Fourier tail. There exists a $p$-noticeable fractional PRG $X$ that $\epsilon$-fools $\mathcal{F}_{a,b}^n$ with seed length $O(\log\log n+\log(a/\epsilon))$ and $p=\frac{1}{4b^2}$.

Note that many well-studied family of boolean functions have exponentially decaying $\ell_1$ Fourier tail. For instance, $\AC{0}$ circuit, functions with bounded sensitivity, functions computed by certain branching programs, etc.

From fractional PRG to PRG

Now that we have fractional PRG for a bunch of boolean function families, the goal is to construct PRG for them. This paper shows how to use fractional PRG to construct PRG for the same family of functions with little blow-up in seed length.

The key idea is using a sequence of indpendent fractional PRG to do a random walk in $[-1,1]^n$ and then rounding to boolean value after few steps. The analysis is based on polarization in one-dimensional martingale. Here, we skip the proof and only state the theorem as follows. Note that we need the function family $\mathcal{F}$ to have some self-trstrictable property in the sense that after fixing some input, the function still lies in the same family.

Let $X_1,X_2,\dots,X_t$ be independent $p$-noticeable fractional PRG that $\epsilon$-fools self-restrictable $\mathcal{F}_{a,b}^n$. When $t=O(\log(n/\epsilon)/p)$, we have $X=M(X_1,X_2,\dots,X_t)$ a PRG that $(t+1)\epsilon$-fools $\mathcal{F}_{a,b}^n$ where $M(\cdot,\dots,\cdot)$ is some random walk function.

Some thoughts

The idea of fractional PRG is quite interesting and it is surprising to me that one can really use it to contruct PRG with seed lengths comparable to other highly non-trivial PRG for various computational models. Also, the recent exiciting oracle separation for $\BQP$ and $\PH$ used the analysis in this paper. I still haven’t fully understood the intuition why their tools overcome the previous barrier and it would be interesting to see if this can be applied in other places.

Another intersting research direction here could be generalizing the idea of fractional PRG as the authors suggested in the end the talk/paper. Basically, the currect reduction from fractional PRG to PRG is via a simple summation and rounding. Could a more complicated composition of fractional PRG be more efficient?

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

Author(s): Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam.

The minimum circuit size problem (MCSP) is a well-known problem in $\NP$ in the situation that people do not know if MCSP lies in $\P$ or is $\NP$-complete. The input of MCSP is the truth table of a boolean function $f$ and an integer $s$ such that the goal is to decide whether there exists a circuit of size at most $s$ computing $f$. Currently there’s no evidence against the $\NP$-hardness of MCSP. The only obstacle in showing MCSP is $\NP$-hard is due to Kabanets and Cai showing that a natural reduction from SAT to MCSP would imply a super-polynomial lower bound against $\mathbf{E}$, the family of problems solvable in linear exponential time.

There are not so many results either even one considers MCSP for restricted circuit family. In 1979, Masek showed DNF-MCSP is $\NP$-hard and this is the state-of-the-art. This paper gives the first improvement for the hardness of MCSP for depth-3 circuit.

Theorem The MCSP for $\text{Or}\circ\text{And}\circ\text{Mod}_m$ is $\NP$-hard.

The main idea is viewing the $\text{Or}\circ\text{And}\circ\text{Mod}_m$ as an indicator function for an union of affine spaces. Concretely, let’s start with $m=2$ where $\text{Mod}_2$ is the parity gate. One can see that the preimage of 1 of each parity gate gives an affine space. As a result, one can think of a $\text{Or}\circ\text{And}\circ\text{Mod}_m$ circuit for boolean function $f$ as using affine spaces to cover the 1-preimage of $f$. Quantitatively, the number of affine spaces needed is a lower bound for the number of $\text{And}$ gates needed.

A story of AM and UNIQUE-SAT

Author(s): Ilya Volkovich.

This paper was presented by Ilya in the rump session. He showed that $\AM=\SBP$ if Unique-Sat ($\USAT$) is $\NP$-hard. Recall that $\MA\subseteq\SBP\subseteq\AM$ and whether $\MA$ euqals to $\AM$ is one of the important question in complexity theory. This paper can be thought of as an indication of $\MA=\AM$. A natural open question after this work would be either (i) improving the assumption, i.e., basing on more believing condition than the $\NP$-hardness of $\USAT$, or (ii) improving the conclusion, i.e., $\MA=\AM$ instead of $\AM=\SBP$.

Let us start with some definitions.

$\MA$, $\SBP$, and $\AM$

One convenient way to view $\MA$ is to think of it as $\NP$ with a randomized verifier. Formally, a language $L$ is in $\MA$ if there exists a polynomial-time computable predicate $R(x,w,r)$ such that \begin{align*} x\in L\Rightarrow\ \exists w,\ \Pr_r[R(x,w,r)=1]\geq\frac{2}{3},\\ x\not\in L\Rightarrow\ \forall w,\ \Pr_r[R(x,w,r)=1]\leq\frac{1}{3}. \end{align*}

As for $\AM$, the verifier (Arthur) will toss the randomness before the prover (Merlin) sends the witness. It immediately follows from the definitions that $\MA\subseteq\AM$. Intuitively, one can think of $\AM$ as a class of languages that have a randomized reduction to $\NP$. Formally, we say $L\in\AM$ if there exists a polynomial-time computable predicate $R(x,w,r)$ such that \begin{align*} x\in L\Rightarrow\ \Pr_r[\exists w,\ R(x,w,r)=1]\geq\frac{2}{3},\\ x\not\in L\Rightarrow\ \Pr_r[\exists w,\ R(x,w,r)=1]\leq\frac{1}{3}. \end{align*}

$\SBP$ is not as well known as $\MA$ and $\AM$ since most complexity courses would not introduce it. However, it is a fairly natural existence between these two very important complexity classes. Let us directly state the definition of $\SBP$. We say $L\in\SBP$ if there exists a polynomial-time computable predicate $R(x,r)$ such that there exists $\epsilon>0$ and $k\in\N$, \begin{align*} x\in L\Rightarrow\ \Pr_r[R(x,r)=1]\geq(1+\epsilon)\cdot\frac{1}{2^{n^k}},\\ x\not\in L\Rightarrow\ \Pr_r[R(x,r)=1]\leq(1-\epsilon)\cdot\frac{1}{2^{n^k}}. \end{align*} It is a simple exercise to check $\MA\subseteq\SBP\subseteq\AM$ by viewing the witness $w$ in $\MA$ and $\AM$ as a part of the randomness $r$.

Intuition for the conditional collapse theorem

We are going to briefly explain the intuition for the following main theorem.

If $\USAT$ is $\NP$-hard, then $\AM=\SBP$.

The idea is actualy quite straightforward. Recall the definition of $\AM$. Suppose for a language $L\in\AM$, each yes instance $x\in L$ has a unique witness $w$. Then it immediately follows from the definition that $L\in\SBP$ by simply let the randomness to be $r’=(w,r)$. Namely, to collapse $\AM$ into $\SBP$, it suffices to transform every language $L\in\AM$ to a language that has unique witness.

With this sufficient condition in mind, it is then no difficult to see that under the assumption that $\USAT$ is $\NP$-hard, one can collapse $\AM$ into $\SBP$.

Some thoughts

This is quite a cute paper that gives a detailed connection between $\MA,\SBP,\AM$. Though the conditional collapse theorem is not too deep after knowing the definitions of these classes, the paper points out a pave to prove $\AM\subseteq\MA$. A the paper suggested in the end, some natural open questions would then be either improving the assumption or improving the consequence. I personally would be more interested in finding more suitable assumption to collapse $\AM$.

References

  1. Carmosino, M. L., Impagliazzo, R., Kabanets, V., & Kolokolova, A. (2016). Learning algorithms from natural proofs. In LIPIcs-Leibniz International Proceedings in Informatics (Vol. 50). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

    Ph.D. 第一年心得

    其實2018 Spring的學期已經結束一個月左右了,也即將要從台灣回去波士頓。來到了一個新的環境求學,在自己不斷繼續成長的同時,要適應新的研究模式、身邊的合作對象、修課方式,甚至是語言還有表達與溝通。一直想要找個機會整理一下這段時間下來的想法,很多不同的思緒混在一起,讓我就這樣不知不覺拖到現在,終於下定決心就不管太多寫就對了。

    Read more...

    Novermber, 2017

    一轉眼已經來到劍橋三個半月了,Ph.D.的第一個學期也即將邁入尾聲,隨著衣服越穿越多,似乎也開始漸漸抓到生活還有做研究的步調。在如此耗腦力的環境之下,了解自己在什麼時候該做什麼事情決定了做事效率,一旦盲目地工作,很有可能最後仍然是一場空。

    現在的生活主要圍繞在三個大方向上面:研究、學習、休息。研究是個需要高度集中力,以及讓思緒自由奔馳的狀態,因此除了需要精神好之外,也很需要一個放鬆自在的環境。也因此當我在想研究的時候,很喜歡四處的移動,通常是從房間開始,播一些輕鬆的音樂,然後好好整理一下之前想過的方向,然後試圖找些可以突破的點,一旦在一個方向卡住一段時間後,就會慢慢的移動到辦公室,或是找個喜歡的咖啡店(尤其是最近愛上了熱巧克力店L.A. Burdick)。最重要的是要邊走邊寫,時常一些盲點都是在邊走邊想的時候釐清的,然後一到下個地方後,就可以把之前卡住的地方寫清楚,然後往下一個方向前進。

    除了研究之外,持續不斷的學習也是身為一個Ph.D.學生(甚至是in general的學術工作者)不可以忽視的一件事情。這學期雖然修了兩門課,但是如果只有把修課該做的事情做完其實是很不夠的。尤其是這邊修課的感覺(至少以理論CS來說)是非常地強調自主性的,老師不會去管你的出席或是預習複習狀況,作業量也沒有想像中的大,不一定需要把上課教的東西完全搞懂還是可以把作業寫出來。這樣的好處是可以讓學生自由的選擇自己有興趣的方向好好的深入學習,而壞處就是學生真的必須要去認真思考自己想要在這門課獲得什麼,不然很容易一下子時間就過去了,然後發現自己什麼也沒有學到。而在課堂之外,學習深度與廣度的增強也是需要依靠每天一點一滴的累積的。看看身邊的senior Ph.D. students,總覺得他們懂的東西好多,不見得是跟他們修過的課或是做過的研究相關,能夠做到這樣的關鍵就是持續一點一滴學習的累積。這有可能是透過聽演講獲得的,也有可能是靠讀paper還有看書學到的。不管是哪種方法,在課堂還有研究之外的學習才是一個人的內功,決定了他可以走得多遠。在體會到這個觀念之後,我開始慢慢規劃讓自己有個固定可以看書或是看paper的時間,目前終於發現在每天的一大早是個很好的時機。也就是在七點多起床到八點多吃飯之間的這一小時,讀一些平常很想看的書(例如代數幾何)還有paper。通常這個時間是個腦袋還沒有很靈活,但是可以正常運作的時間,拿來學習可是最剛好不過的了。

    在研究還有認真學習之外,生活的平衡也是維持健康的身心不可或缺的一部份。這學期做了大量的課外活動,試圖在研究學習還有生活之中找到平衡。有時候覺得自己相較於同學朋友之下有點太混了,不過說實在跟剛開學時很拼的時期比起來,我感覺做事的效率還有成果沒有差太多。”適當”的放鬆對我來說的確可以讓我在該認真的時候更能夠專注,把事情有效率地做好,同時也更享受在劍橋舒服的生活。

    雨後讀不下書的夜晚

    連續下了幾天雨的劍橋,就跟梅雨季的台北差不多令人鬱悶,開學的第三週,齒輪漸漸進入了軌道。五年的Ph.D.看起來很長,但是看看身邊的學長學姊們,似乎看見了一年後、兩年後、三年後的自己,不久後也要站到他們的位子上了。

    讀書和學習最大的壓力始終是來自自己,第一個月還沒過完已經開始有點胃痛了,也不知道是因為最近太常自己做菜為,衛生沒有做好。還是給自己的目標訂太高,太在意和別人的差距,太急著想要有點明顯的進步。明明知道不要給自己太多壓力,五年慢慢的來,享受這一切過程,但是每當和別人討論時無法清楚地理解,沒辦法提出好的問題,都還是會很不甘心,覺得自己要更好。

    看來還是不懂得接受失敗吧!

    上海特訓班

    去年上海財經大學成立了理論計算機科學研究中心,由陸品燕老師領導,目前已經有五位全職的老師/研究員,再加上每年暑假期間絡繹不絕的訪客,這裡儼然成了東方理論計算機的新星。

    去年暑假我就和鐘老師來這邊拜訪了兩個禮拜,事隔一年,在將要去美國攻讀Ph.D.之際,再次重遊。雖然和這邊的學生老師交流沒有預期的多,但是和同行的鍾豪還有鐘老師將近兩週來的密切相處,還是讓我在研究還有思想體系上有了些成長。

    Read more...

    與Bell's inequality的約會

    這週末趁著去上海前的空擋,到台南四天三夜拜訪親朋好友,七月底去唸博士班之後,見面將變得不這麼容易了,雖然這幾年縱使在台灣也是聚少離多就是了。

    阿霈是我在高中時的摯友,我們倆當時都熱愛物理,雖然喜歡的方面可能不太一樣(我比較偏向喜歡物理中數學的漂亮)。還記得那時候阿霈就是個對理解東西很固執的人,在台灣高中教育的氛圍下,大部分人講求用最快速的方式把知識記起來考高分,但是阿霈總是會很鑽牛角尖的想要徹底理解清楚。當時還覺得他有點奇怪,現在反倒是很羨慕他很早就有著批判學習的精神。

    Read more...

    寫於柯潔戰敗後

    如同眾人意料中一般,20年前深藍(Deep Blue)擊敗人類西洋棋王Garry Kasparov,這一天,AlphaGo擊敗了人類圍棋第一的柯潔。從兒時的故事,到親眼隔著螢幕看到淚灑黑白之間,心中雖然不意外,但仍然震驚於這一天如此快的到來。

    從小的時候就受爸媽影響開始學圍棋,雖然自己下不出來,但是看到高手過招,還是能夠欣賞每一步的奧妙(這也是$\P\neq\NP$的一個例證吧!?)。還記得約莫在升上國中左右的時期,電腦圍棋開始漸漸普及,在家連個網路就可以和來自世界(其實也就只是中日台韓)的網際對弈,也因此越來越不去棋院了。有時候一時之間在網路上沒有配對到對手,又棋癮發作,就會點開電腦自動下棋模式,然後狠狠的把電爆對手。還記得國中的我可以讓當時網路上最厲害的程式兩三子,仍然輕鬆獲勝。

    Read more...

    5/14 - 5/21, 2017

    最近的學習是在五花八門的混亂,還有鑽牛角尖的細節中來回交替。因為下定決心想要在九月開學前好好把一些基礎學好,於是列了一大票學習清單。一兩個月下來,每個好像都讀了一些,細節也學到了不少,但是又好像都沒有把整個經脈打通,這感覺有點像一個棒球選手把內野、外野、投手、捕手的基礎的摸一遍了,但是還是沒有能力上場打球。每天看著精彩的球賽不斷上演,卻只能在板凳繼續打轉。

    Read more...

    鴻門宴

    今晚有一頓免費的日式料理大餐,滿心期待的踏入捷運,坐在位子上聽著熟悉的貝多芬第四號鋼琴奏鳴曲,大小聲精細的轉變依然令人不自覺搖擺身體。忽然一陣念頭襲來:為什麼這麼突然要請客呢?該不會是場鴻門宴吧!?

    Read more...

    等效不等式 (Isoperimetric Inequality)

    \begin{equation} \int_{\mathbb{R}^n}\card{u}^{\frac{n}{n-1}}\leq n^{-1}\omega_n^{-1/n}\int_{\mathbb{R}^n}\card{\nabla u}. \end{equation}

      球
      在歐式空間中
     如同他圓滾的外觀
    竭盡所能的向外擴張
     用力嘲笑正立方體
      不懂利用有限的
      空間

    \begin{equation} \gamma_s(\partial A)\geq\phi\circ\Phi^{-1}(\gamma(A)). \end{equation}

     在 高 斯 世 界
     半 空 間 是 座
     無 止 境 高 牆
     任 何 戳 打 槌
     仍 矗 立 挺 拔

    2017 Ph.D. 申請心得

    從大三開始漸漸有了想要出國留學念博士的想法,經過一兩年在各個實驗室還有不同領域的歷練後,在大四的寒假下定決心要申請theoretical CS (TCS)相關的博士,並且目標鎖定在Harvard。從去年(2016)九月開始,與幾個同屆要申請的好友,還有許多學長、老師、家人的幫助之下,終於完成申請,並且熬過了痛苦的等待放榜的冬天,最終要如願在今年(2017)秋天到Harvard念博士囉!

    Read more...

    Visit Day @ Harvard University

    Harvard基本上是我一直以來的top choice,首先收我的Boaz Barak是我最想跟的教授,然後這邊也還有另外幾個我感興趣的老師像是Madu SudanSalil Vadhan,加上離MIT很近,可以和那邊互動也是一個大加分。在visit day之前,我的想法是如果Harvard沒有讓我覺得有扣分的地方的話,那就是會選Harvard了。

    Read more...

    Visit Day @ UT Austin

    UC Austin是這次參訪的四間學校中最炎熱的一間,幾乎跟台灣有得比。這邊理論CS的老師總共有九位,而且各自做的領域蠻diverse,其中Dana Moshkovitz是我最有興趣也是當初最先聯絡我的老師,而且她的老公Scott Aaronson更是理論CS界的奇葩,是個什麼都做什麼都厲害的人,因此就老師層面而言,UT Austin和Harvard是我主要考慮的兩間。

    Read more...

    Visit Day @ UCSD

    UC San Diego(UCSD)位於美國西南角靠太平洋和墨西哥的溫暖地區,擁有龐大且diverse的理論CS團隊,和數學系也有緊密的合作關係,雖然學校排名看起來普通,但是據他們所說,這幾年整個學校有往前衝刺的跡象。

    Read more...

    Visit Day @ Princeton University

    Princeton是理論CS特別是complexity theory的傳統強校,而且離高等研究院(IAS)距離十分鐘的車程,再加上位於兩座大城:紐約和費城中間的優雅寧靜區域,是個適合做理論研究地方。

    Read more...

    搬家

    搬家了,是有記憶以來第四次搬家,雖然這個家是住最短的一個,但是實際參與了搬家的過程,卻反而感觸特別深刻。

    Read more...

    Test Math

    This post aims to test the math environment on this website.

    Read more...

    主動學習者計畫 - 期末心得

    隨著梅雨季的到來,為期八個月的主動者學習計畫也將要劃下句點,規劃了三個多月的期末專文及心得總結:《探索計算的極限》也終於如期完成,看著這些一點一滴累積下來的成果,心中實在是既感動又興奮。

    Read more...

    第二十二週回顧

    最近自主學習的進度來到了隨機抽出器(Randomness extractor),實在非常的神秘,在這邊簡單記錄一下目前看完的心得。

    Read more...

    第二十一週回顧

    最近除了正常的讀書做研究之外,大部分的時間都花在寫文章上面,而在數次的閱稿餐會中,讓來自不同背景的朋友看看我寫的文章,才發現原本我覺得很平易近人的內容,其實大家的感受都差很多。最明顯的例子就是介紹一個新觀念的方法,我在介紹一個新的東西時,會很習慣從比較高觀點,或是抽象的角度做宏觀的解釋。有時候自己掌握的不太好,就會變得有些虛無縹緲,讓人抓不到重點,在幾篇設定為大方向介紹的文章中就很明顯地出現這種情況。於是這時候幫我試讀的朋友就會很痛苦,紛紛向我抱怨沒辦法抓到我想要表達的重點,看過去覺得講的內容頭頭是道,但是看完後卻覺得沒有實際接受到什麼內容。

    Read more...

    第二十週回顧

    雖然最近被研究還有寫文章佔據了大部分的時間,不過靠著番茄工作法(Pomodoro Technique)的幫助,讓我可以在很大塊的忙碌時間中,抽取出小塊小塊的零碎時間,來完成其他的事情。這對於自主學習計畫的進度,或是修課的複習、功課等等,都有看起來雖小,但是重要的關鍵影響。

    Read more...

    第十九週回顧

    這禮拜開始嘗試用一個電腦的App(Pomodone)來監測我的時間分配,然後發現的確出現不少的問題。首先是時間分配非常不均勻,我花了超過三分之一的時間在圖論上面,因為這門課每個禮拜都有五到六題的作業,而且最近的題目困難到連我要把解答看懂都要花很久的時間(因為大部分的題目都是十幾年前人家的一篇論文…)。於是這樣弄下來,我平均一個禮拜不算上課大概都還花了十五個小時在上面。

    Read more...

    第十八週回顧

    這是一個非常飽滿的禮拜,禮拜一大部分的時間都在處理研究還有跟老師討論,禮拜二則是花了一半的時間準備讀書會要報告的講義,禮拜三則是從早到晚滿滿的行程,禮拜四下午進行了這學期第一個期中考,一直到了禮拜五才終於有喘息的空間。

    Read more...

    第十七週回顧

    這禮拜是個忙亂的一週,兩個作業的死線把讀書的計畫稍微打亂了。再加上週末回台中看棒球校隊打大專盃複賽,更加壓縮了原本的自由時段,所以這禮拜的自主學習計畫就只有完成了一半。

    Read more...

    第十六週回顧

    隨著新學期的開始,除了原本的自主學習計畫之外,又多出了幾個新的主題想要涉獵,有些是之前有簡短看過一點的,有些則是完全陌生的領域。最後我決定除了原本進行的這兩個課程之外,再另外加上兩個自學的支線,一個是UC Berkeley的Luca Trevisan教授在這學期開的Graph Partitioning, Expanders and Spectral Methods,另一個則是UIUC的Yihong Wu教授開的Information-theoretic methods in high-dimensional statistics。

    Read more...

    第十五週回顧

    這禮拜開始著手規劃撰寫計算理論相關的中文科普文章,約到了三位背景不太相似的朋友要在禮拜日幫我審閱試寫的四篇文章。希望可以先將目標的對象還有寫作風格確定下來,瞭解一下適合的文章內容、長度等。此外,我也簡單列出了可能的寫作大綱,目前計畫分成兩大部分,第一部份是基礎背景的介紹,讓原本對於資訊理論不熟的人,可以認識基本的概念和定義,這樣在第二部分的專題介紹中會更能抓住核心的蓋念。

    Read more...

    第十四週回顧

    這禮拜是期待已久的開學週,在台大的最後一個學期,修課數量明顯的減少,從以往大約5-7門的主科到這次只有三門,不過這三門都是我很熱愛而且扎實的課(有兩門課每週都有作業!)。此外還很幸運地選上咖啡學和音樂欣賞,看來這學期將會有充實的知識饗宴,又有豐富的感官享受!

    Read more...

    第十三週回顧

    經過兩個多月的努力,自主學習計畫的第一階段終於順利的如期完成了!看著一篇篇的筆記還有回顧心得,除了感嘆時間過得很快之外,也很替自己感到高興,能夠在期末考的壓力、全家出遊還有過年的外界誘惑下把預計的進度看完。這一個階段很多的教材是我在去年暑假就一直想要看,但是斷斷續續沒有完成的部分。透過這次自主學習計畫,一半靠自己的毅力還有一半的心理壓力,雖然中途有幾週延誤了進度,最後還是衝刺補了回來,算是達成了以前做不到的任務了吧!

    Read more...

    第十二週回顧

    才覺得寒假沒開始多久,農曆新年就緊接著來了,雖然這幾年越來越沒有像小時候那樣過節的氣氛,但是每年到了這個時候仍然都是最放鬆的時刻。今年春節的作息比較一致,每天起來吃個早餐開始唸一些書,泡完咖啡後再唸一下書,中午和家人聚餐吃飯聊聊天,午覺後再繼續唸書,晚上可能會看個電影或是影集,睡前再看看小說。生活被書本、食物和電影填滿了,三個都是我最喜歡做的事情,這樣的日子過得還真是愜意呀!

    Read more...

    第十一週回顧

    這禮拜計算理論和pseudoransomness的進度都分別來到最精彩的部份,前者進入「代數複雜度」(Algebraic complexity)的領域,目標是研究進行平時常見的代數運算所花費的計算複雜度,很神奇的是前人把這些看起來與電腦習慣使用的0,1位元運算做了很深刻了連結,提出了對應的複雜度類別,讓人們可以對最直接的數學運算做分析,不必再將問題轉換成電腦可以表達的方式。

    Read more...

    第十週回顧

    上禮拜結束所有的期末報告之後,正式來到了大學生涯最後一個寒假。雖然是個假期,但是對於準備要申請國外研究所的我來說,這是當兵前最後一個空擋好好為接下來的研究還有課業打穩腳步。除了持續進行原本的自主學習計畫之外,這段期間還多了一個重要的學習目標:代數。因為在幾個月前得知當我放棄雙主修數學系改成輔修之後,原本可以抵免系上的線性代數課程變成無法充兼數學系的輔系必選學分,也就是說我必修再多修一門代數相關的課程。為了要拿到數學系的輔系,我必須跳過代數導論上,直接挑戰下學期的代數導論下!之前聽幾個雙主修的同學聊過代數導論這門課,大家紛紛認為是一門很硬不容易讀的科目,看來下學期除了自己的研究之外,在修課方面也會面臨不小的挑戰。

    Read more...

    第九週回顧

    繼上週期末考造成進度拖累之後,這禮拜面對的是五天四夜的家庭旅遊,再加上禮拜五下午有一個期末口試和報告,自主學習計畫面臨嚴峻的考驗。

    Read more...

    第八週回顧

    當初在規劃進度的時候,特地設想到期末考中可能會有許多無法預期的事情發生,很可能沒辦法專心的學習新的範圍,因此故意把複習週排在這個時間點。而的確這禮拜因為一些煩心的事情,還有考試及meeting,進行的不是很順利。前四天下來,除了想了一些題目之外,幾乎沒有把之前的落後的進度補起來。再加上禮拜五回家、禮拜六投票日、禮拜日出發去家庭旅遊,即使在沒有多餘進度安排的情況之下,這禮拜的複習還是失敗了。

    Read more...

    Day 1: 彩虹、台東市、雨過天晴

    早上六點半,準時被媽媽叫醒,五天四夜的花東埔里之旅即將開始。

    Read more...

    第七週回顧

    期末考前的一個禮拜,是最輕鬆,也是最讓人無法專注好好把一件事情完成的一週。這次的進度來到了我之前就很有興趣的主題:互動式證明(Interactive Proofs)。在二十多年前,$\IP$(Interactive Proofs的一個複雜度類別)被證明出和PSPACE(多項式空間複雜度)等價時,正式宣告了相對化技術(relativization technique)的死刑,並且開創了一個新的可能,緊接著Arora也發表了著名的$\PCP$定理,利用互動式證明的概念,將$\NP$定位在$\PCP(\log n,1)$,讓人們一度以為有機會解決$\P$ vs. $\NP$的問題,不過二十年過去了,$\P$ vs. $\NP$仍然懸而未解,倒是互動式證明的概念帶起了許多近代密碼學重要的概念。

    Read more...

    第六週回顧

    2015 年的最後一個禮拜在放榜的緊張情緒,還有三連假的悠閒中度過了。公費留學考試在這幾年刻意將放榜的日子選在12/31號,就像大學指考的放榜選在父親節一樣,讓大家在特別的日子中面對人生中重要的結果出爐。

    Read more...

    第五週回顧

    隨著年底的到來,時間果2015 Xmas然過得特別快,事情也令人多的感覺做不完。這禮拜身邊歡樂的氣氛讓自己稍微鬆懈了一下,同時週末要回家一趟,事情將要無法順利做完是意料中的事。看著行事曆一排排的死線,心中又很想要一些別的東西,做一些別的事情,真是左右為難啊!

    Read more...

    第四週回顧

    這禮拜進入了自主學習者的第一個緩衝週,基本上因為進度都有跟上,所以這週大部份的時間都是花在做習題。然而事情沒有計畫的簡單,Pseudorandomness的習題大部份除了有很多小題之外,大多都需要一些全新的想法才有可能解得出來。像是第二章第九題的Spectral Graph Theory,那六個小題基本上就是那個領域最開始一些創新想法的簡單版,幾乎都需要一點點巧思才有可能解開。不過也因為如此,多少有訓練到自己看問題時的開放思維吧!

    Read more...

    第三週回顧

    這禮拜在不知不覺的匆匆忙忙中結束了,相對起來主動學習計畫的執行顯得比較慌亂一點,有超過一半的內容是邊吃飯邊看過的,習題大多也是在搭車的路上,或是騎腳踏車的時候想。該看的都還是有看完,不過就沒有時間好好整理一下,題目更是沒有完整的時間好好思考,這大概就是沒有排每週固定時間的下場吧!

    Read more...

    第二週回顧

    這禮拜是NTU Active Learner計畫的第二週,果然和預期的一樣仍然充滿了幹勁,不知道一個月後是否還能維持呢?

    Read more...

    第一週回顧

    這禮拜是NTU Active Learner計畫的第一個禮拜,整體看來都在進度上,同時也在禮拜一的時候架了這一個部落格,接下來一些學習的心得,還有計劃遇到的困難等等都會記錄在這邊。

    Read more...