$ \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} $
Back to blog

Ph.D. 第四年心得

(See here for an English version)

又一陣強風吹了過來,汗水中摻雜的鹽分刺得讓眼睛睜不太開。再怎麼努力地划著槳,船身卻總是不受控制的忽左忽右。看著身邊的兩座小島,感覺小船不但沒有前進,甚至還被風往後吹了幾公尺。半小時前才毫不猶豫地決定在回程前繞一圈Graham lake中的第二小島,看看傳聞中的老鷹巢,轉眼間,突然捲入湖中心的風暴之中,使勁了全身的力量,只能勉強維持小船的基本平衡。在一旁盤旋老鷹,就像是在看好戲般,默默笑著誰叫我們打擾了他的悠閒時光。

幾週前趁著STOC期間大部分的meeting都取消了,和室友伉儷還有Brabeeba來到北邊緬因州的幾個小鎮,來趟久違的escape trip。就如同疫情來得突然,美國這邊解封的速度也快的讓人措手不及。在短短一兩週內,人們不再戴著口罩,幾乎所有的室內活動都正常開放了。而心裡的適應速度也是慢了半拍,還是多小心翼翼地待了好幾天的口罩,直到連續多天看到Cambridge零確診的強心針,才害羞的漸漸收起了口罩。重新讓整張臉展現在公共場合中,一開始還真的有點憋扭,像是第一次赤著上身跑步的感覺一般。直到開始會和雙眼對到的路人微微一笑,才意識還有接受到,正常的生活終於回來了,喔不應該說是新的後疫情生活已經開始了。

不過原本預計的放鬆耍廢之旅,卻由第二天早上的四小時湖中受困記拉開了序幕。也許看似和本文的主題無關,這意外的插曲卻和我四年來的Ph.D.旅程驚人的相似。從一開始坐上船拿著槳興奮地面向壯闊的湖景,接著在一小段不太輕鬆,但還算游刃有餘的航程來到了岸邊在地人提到的老鷹巢。突然風向一變,讓回程的目標看的到卻總是無法靠近。不斷地重新規劃回去的可能路線,卻發現理論總跟不上實際的狀況,一下子飄去了鄰近的另外一座島,眨眼間又被吹回老鷹巢之島,更多的時候則是在原地打轉。眼看太陽越升越高越烈,不禁開始懷疑自己真的回得去嗎?好在身後有個可靠的小夥伴—Brabeeba,在互相打氣還有互補的合作之下,緩緩地朝著目標前進。在風大時,努力試著維持平衡,不要倒退太多。趁著風小之際,全力衝刺,滑幾公尺是幾公尺。當離岸邊越來越近,才逐漸發現水上的距離感和陸上是多麼的不同。總以為再五分鐘就到了,用力衝刺一段之後卻又失望地發現眼前的景色沒什麼變化。而目的地的細節也是到最後幾刻才突然浮現清晰,最後更是在沒有絲毫準備的狀況下,突然一鼓作氣衝上了岸。

意外的湖中受困打攪了原本對湖邊生活的浪漫想像,在木屋中狂吃零食補充能量之虞,更是不斷發誓再也不划船了,並擔心著隔天將要全身痠痛破壞剩餘的假期。不過當隔天清晨在鳥鳴中醒來之後,在湖邊冥想靜思之際,又不小心愛上了大自然的深邃與靈性,身上的肌肉也沒有預期的疲憊,似乎在悄悄問著下一段旅程將在何處?

如今走完Ph.D.前四年的我,就像是個剛剛划完一座小湖上岸的小男孩,顫抖地望向壯闊的世界。心中對自我能力的懷疑多少還是有些,也許甚至多了對於之前的目標短淺的失望。熱情可能不再如此激動,但是變得更加圓潤和堅定。下一趟旅程在哪裡?這將是個不停的問題,而確信的回答是,我將會不斷地繼續往前走下去。

在下一段旅程開始之前,也讓我在這邊記錄一些近幾個月來的一些雜想。

這一年發生了什麼?

持續的疫情讓日子少了變化,時間也不自覺過的飛快。相較於前幾年的各種成長與挑戰,這一年就像是把準備好的食材放進了烤箱等待出爐,並同時思考著下一道菜要做什麼。

在學習上,我還是很不習慣線上課程,總會不小心恍神錯過一些重點,而下課後看著同學們一個個離開zoom的身影,更是懷念起以前在走廊間討論課堂內容的時光。連續助教了兩個學期的課(Spectral graph theory和Complexity theory)還有一個為期一週的暑期課程,隔著螢幕和學生的互動總是讓人覺得少了什麼,沒辦法再從教室的最後面觀察每個學生的學習狀況,助教時間也很難同時顧及每個人。過去當翻轉教室開始盛行時,還以為線上課程將可以慢慢取代實體課程,直到這次疫情造成的大封鎖,才讓人體會到現實世界中人與人之間的互動不是那麼容易被取代的。

不過這些教學經驗可以說是在疫情間對我來說很重要的精神糧食,學生們對知識的好奇與渴望重新喚醒我當初對於理論CS的熱情,看到學生慢慢的成長還有提出各種有趣的問題,更是有股做研究無法產生的成就感與快樂感,堅定了我未來想要走向教育&學術之路的信念。

至於研究方面,去年有許多突破的兩個方向都還持續有些後續的進展,陸續寫了幾篇論文,不自覺時間一下就過去了。當後續的研究仍然如火如荼的展開時,我突然意識到自己對於所產出的研究結果並不再那麼的興奮了,而且花在原本最感興趣的問題上的時間越來越少,更別說是閱讀新的知識還有思考研究背後的大方向。望著所剩不多的博士生涯,我又陷入了一陣迷茫,不確定該如何妥善地分配時間。

觀察身邊其他的博士生還有博後,主要有兩種時間分配的類型:第一種我稱之為貪心演算法(greedy algorithm),遇到什麼做得動的研究問題就傾全力付出,並且把後續的問題做到完為止。第二種我稱之為理想主義者(idealist),只花時間在自己非常感興趣的問題,不太在意表面上的產出與進展。當然,絕大數的人其實是混合了這兩種風格,不過在我的觀察之下,感覺能夠最後生存下來的人通常都是極端地採取兩者之一。這兩種類型沒什麼優劣之分,而且都對科學研究的進展有不一樣的貢獻,學術界也的確需要不同類型的研究者。但是很顯然的我目前處在的是一種很尷尬的中間狀態,我是不是該想想什麼路線是比較適合自己的呢?

除了在研究方向和風格上開始有了許多meta-level的思辨,在這一年中我也思考了許多關於科學研究的本質、不同領域的異同、人的弱點等等的哲學問題,在剩餘的篇幅裡就讓我粗淺的試著把腦中混亂的想法整理一下。

不同科學領域的異同

自從兩年前開始接觸物理和腦神經科學的研究之後,我開始漸漸意識到不同的科學方法、目標、哲學可以差得非常多,有時甚至會稍微互相摩擦衝突。例如在理論CS中,一個研究如果沒有完整扎實的數學證明是不太可能獲得領域的認可,但是同時大家對於研究的結果(e.g., 證明出來的定理)和現實應用的相關性要求就非常低,有時還可以聽到「太考慮應用就不是做理論了」的言論。而在理論物理(以我粗淺的認識)中,對於數學嚴謹度地要求相對沒有那麼絕對,一個常見的做法是對一個簡單的情況有個完整的理論分析,然後再對複雜但是貼近實際的情況做電腦模擬來論證提出的理論。至於腦神經科學,即使是我看過最嚴謹的理論研究結果,通常都還是停留在使用模糊數學(fuzzy math)的階段,著重的是在實驗的設計以及如果解釋實際觀察到的現象。

我很喜歡朋友Lisa用知識樹來視覺化不同領域結構的不同:數學和物理像是聳立的神木 擁有幾個世紀的知識累積,不但有許多分支,分支之間還會互相連結,而且許多枝枒延伸的非常長。電腦科學則有點像是二元樹(binary tree),在近年來有著爆炸式的成長,枝枒分散得非常快,但是相對來說比較少很長的分支。而生物學則很像是一群灌木叢,觸及非常多觀察和問題,但是不同子領域之間相對比較難有統一的理解。

這樣的截然不同,部分是來自於領域發展和演化的過程,部分則是來自領域研究對象本身的性質。對電腦科學來說,研究的對象能夠被數學完美刻畫於是更能夠承載簡潔漂亮的數學理論。而物理和腦神經科學面對的是複雜多變的大自然,也因此在數學化的過程相對更加具有挑戰性,有時候我甚至懷疑,生命科學真的有可能具有如同電腦科學或是物理學般的美妙數學理論嗎?

最近參加了一個生物哲學的讀書會,在拜讀演化生物學大佬Ernst Mayr寫的『這就是生物學 (This is Biology)』,想要建構一下我對生物研究的基礎信仰。目前計畫再過幾週讀完全書後,另外來寫篇文章講講我對科學研究的想像,以及剖析理論及抽象思考在生物研究中的可能性!

開放的心胸以及溝通的重要

身為在學術界還很資淺的研究生,當在一個領域稍微站穩著腳之後,反而容易過度戴著所屬領域的有色眼鏡去看不同的學科。有時候是單純的不了解,例如即使看了兩年多的腦神經領域相關的論文,我至今還是時常無法理解為什麼有些研究結果被視為是重要的。有時候則是思考角度的不同,像是CS的人習慣非常「演算法式」的思考,而物理和數學的人則常常想著對稱與和諧。但是如果硬要將一個領域的思維方式強加到另一個領域之上,不但很難成功,同時也可能會非常的冒犯。正因為如此,我開始慢慢體悟到在科學研究裡,保有開放心胸的重要性。這不是說一個人必需去理解其他領域的方法論,而是說我們該放下領域間優劣的比較心態,接受學術界的多樣性!

甚至先不論跨領域研究,即使是在原本的小領域裡,能夠理解包容不一樣的研究方式和結果也是非常重要的。在過去這一年中,我自己就因為研究習慣的不同,不小心冒犯到合作的對象:我習慣先抓到大方向的證明思路,接著再把每一個步驟的細節搞清楚,然而有些人習慣扎扎實實的一行一行弄懂證明。這兩種不同的研究風格在理論CS都很常見,而且可以說是很好的互補搭擋。不過之前我太過於預設所有人都是屬於第一種類型的研究風格,使得屬於第二種風格的合作者很難理解我在說什麼,造成溝通還有合作上的障礙。直到有一次找個機會好好聊了一下,互相理解對方想事情的方式,找到合適的溝通模式,才化解長久癥結的問題。

從這些大至領域間的語言隔閡和小至個人的風格差異,讓我體悟到科學(或是說學術研究)一個非常可貴但是常常被忽略的特性就是「溝通」。在理想的情況(實際情況是不是這樣就難說了…)之下,科學和傳統教條很不同的地方就在於沒有權威,注重實證和開放的辯論。當然這是最理想的情況,現實中的學術圈可能沒有如此的美好,尤其是當成為科學家變成一件相對普及和容易的事情之後,人與人之間的競爭惡鬥污染了這個理想的烏托邦。不過和許多失敗的烏托邦不同的是,在學術界中,試著加強自己的溝通還有包容能力,基本上不會是件壞事(也就是比較不會有囚犯困境的現象)。

不過當我跟身邊一些做研究的朋友提到溝通在科學中的角色時,有些人會質疑,如果太想要讓別人理解和欣賞自己的研究,反而可能失去自己創作的核心價值。比較激進一點的人甚至會覺得沒有把研究寫成論文的必要,好的研究結果應該是不證自明的,花那麼多時間把論文寫好是在浪費其它做研究時間。首先,我覺得保有自己思想的獨立性和增加作品的客觀理解性並不相互衝突,很多時候再寫論文或是解釋理論給別人聽的時候,甚至還可以讓自己的理解更加深刻。再者,我覺得科學與藝術最大的不同就是,科學在本質上追求的是客觀,而藝術則是包容主觀的多元自我表達。要達到理想中的客觀性,溝通就成為非常重要的一步,在現代科學界中寫論文則是其呈現的方式(不過當然有可能在五十年後會有個比寫作更好的方式出現!?)。

深入的理解(Deep understanding) vs. 清晰的理解(Clear understanding)

不知道從什麼時候開始,我對於深入的理解(deep understanding)有了種莫名的追求。也就是說不管看到了什麼問題,我都會下意識的先評價這個問題夠不夠深入(deep),並且對於我認為不夠深入的問題嗤之以鼻。這樣的追求不知不覺過度的影響了我的生活,我甚至會開始對於別人的研究或是其他領域的問題品頭論足,而且越來越眼高手低。直到我講話的內容越來越抽象,連幾個平時很了解我的朋友和合作者都開始不太理解我在說什麼時,我才意識到自己有點走火入魔了。

什麼是「深入(deep)」?存在一個客觀的尺度來衡量深入與否嗎?深入的理解是衡量一個科學研究優劣的標準嗎?不同領域間要怎麼評價彼此的深入與否?當回頭思索這些基本的問題之後,我才體悟到「深入」就像是「有趣(intersting)」是一個太過主觀,甚至在使用不恰當時可以帶有攻擊性的詞彙。也許我的初衷是關於科學家對研究課題追根究底的精神,但是將之化為具體的評價後,不但讓我變得有點好高騖遠,還變得有點憤世嫉俗。

但這並不是說追求深入的理解錯了,而是更該小心拿捏尺寸。同時,我發現一個作為深入理解很好的替代原則:追求「清晰的理解(clear understanding)」。仔細回想看看以前求學時做題目不斷做錯,或是做研究想問題卡關,甚至是平時處理日常瑣事陷入無解的迴圈,這些情況有什麼共同的地方?我覺得基本上都是源自於沒有理解清楚事情背後的原理或過程。在日常生活中也許不太需要把所有事情都弄清楚,就可以活得好好的。然而這樣子的偷懶累積多了之後,有時候就很可能形成問題。當面對這些類似的難題(例如報稅…)時,往往可以在退一步釐清問題脈絡後迎刃而解。同樣的原則也很適用於科學研究的前線:回首檢視那些當年重大的科學突破,除了有一部份源自於靈光一閃之外,其他往往是科學家不滿意於當下的理解,在把問題越想越清楚的過程中找到了解決的辦法。換句話說,清晰的理解是種追求知識上誠實(intellectual honesty)的態度。也許當理解清晰到一定程度之後,自然就會成為深入了理解了吧!?

人的弱點與自我、感性與理性

自從發覺自己在抽象思考方面走火入魔之後,我和好友Juspreet有了非常多關於「人」的討論。由科學帶來的「人定勝天」信念還有現代社會越趨機械式的生活模式,不知不覺讓人們越來越像一台台理性的機器,忽略了我們終究是人類,活在這個現實世界中。培根(Francis Bacon)曾經說過

Nature, to be commanded, must be obeyed.

如欲掌控自然,必先服從之。

Francis Bacon, Novum Organum

同樣的,身而為人,我們該謙卑地知道且面對自己的弱點,或是說自己的本質。

Juspreet對我提出了兩個觀察:第一個是他發現我非常在意別人的感受(但這不代表我很會察言觀色…),同時也很容易受到別人行為的影響。如果在一個大家都很坦白直率的環境下(例如我和Juspreet之間的相處模式或是在比較prefessional的合作上),這樣的性格不會造成太大的干擾,因為大家有話直說,有問題和糾葛馬上說清楚解決。然而在很多時候,過於坦白直率是不見得受歡迎的,甚至有些人會為了表面上的和諧先默默容忍,讓潛在的問題成了未爆彈。如果不在意他人的感受,這些未爆彈也許不太會造成什麼傷害,然而如果同時重視對方的感覺但是又習慣直來直往的,那麼就很容易陷入進退不得的僵局。在這過去這一年中,無論是生活上或是研究的合作中,我都因為這樣的個性受了不少折磨。

好巧不巧年初我重新翻了一本多年前買的書:『好人總是自以為是:政治與宗教如何將我們四分五裂(The Righteous Mind: why good people are divided by politics and religion)』,意外地提供了我許多角度來思考這樣子的個性。作者Jonathan Haidt是個道德心理學家,在這本書(以及先前的幾本著作)提出了一個令人耳目一新的架構來描述理性與感性(在書中對應到”直覺”和”情緒”)的共舞:有別於主流科學界中對於理性主宰的看法,作者傾向哲學家休謨(David Hume)的想法:理性是情緒的僕人。運用了大量的心理學實驗,甚至一些社會學和演化論的觀點,作者精彩的解釋了在各種不同情況下,我們的情緒是如何先受到了刺激,因而掩蓋了理性思辯,最終進一步的在政治或是宗教的議題上產生衝突。

同樣的概念也可以用來解釋許多生活上的不愉快,以及研究合作中的摩擦。在討論中如果嚴苛地否決了別人提出的證明想法,是不是會不小心讓對方不好受?在寫論文時直接把其他合作者寫的內容刪掉重寫,會不會讓人覺得被冒犯?在解釋證明的時候沒有耐心、不嘗試理解對方有沒有足夠的背景知識,會不會讓人感到被污辱?更重要的是,當上述的情況發生時,再怎麼解釋自己的動機是無意傷害他人的,都已經於事無補,畢竟被傷害是主觀的。

而這就和Juspreet提到的第二個點很相關了:自我(ego)。雖然我很在意別人的感受,有時候也知道為什麼別人會有某些行為和反應,但是我通常會很難接受別人不用我覺得比較好的方式做事情。換句話說,我理性上可以理解他人行爲背後的來龍去脈,但是感性上我會無法認可,這完就就是同理心(sympathy)和同情心(empathy)的差別。

所以除了透過閱讀還有溝通理解別人的感受之外,我更需要加強的是放下心中很強烈的自我,發自內心地接受多樣性,這剛好就是這陣子來我從生物學還有大自然學到寶貴一課!

結語

不知道是不是受了疫情還是前陣子讀的一本小說的影響,在這一年中我開始用許多不同的角度重新面對研究以及生活。時間沈默但穩定地流逝,世界喧鬧且不受控地改變,身在其中的我們一邊需要堅強地站穩腳步甚至維持向前的速度,另一方面則不可忽視內心積累的困惑與吶喊。在滿足生存基本需求、填補漫漫光陰與展現自我之間的循環,有時我們陷入太快太深的漩渦而暈了頭。想清楚自己的長處和弱點是什麼、自己適合的style是什麼、對自己來說最重要的東西是什麼,也許值得在努力不停向前划行時,停下來好好思索、重新定錨。