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

My Fourth Ph.D. Life

(中文版原文連結)

A sudden gust of wind came out of nowhere, blowing sweat into my eyes and almost making me burst into tears. No matter how hard I pedaled, the canoe was uncontrollably swaying like a snake. Looking at the two little islands beside me, I felt as though the canoe had not been moving forward but had been blown a few meters back by the wind. Just half an hour ago, we had decided to circle the second island of Graham Lake and see the eagle’s nest before going back. Suddenly, we were trapped in the middle of the lake by a mysterious windstorm. Even straining all the power from our bodies, we could barely maintain the balance of the canoe. The eagle hovering nearby seemed like an outsider watching our misery and laughing at us.

As most of the meetings this week had been canceled for STOC, my roommate, his wife, Brabeeba, and I took a long-awaited escape trip to the north. Like the quarantine had come all of a sudden, the reopening in the US was also surprisingly fast. Within a week or two, most people on the street no longer wore masks, and most indoor activities had resumed. It took me a few more days to adapt to the “new life” after seeing zero COVID cases in Cambridge in a row. Putting the mask away and showing the whole face in public had never been this awkward before, like the first time running without a shirt on. Not until I began to smile at the pedestrian did I realize that normal life was finally back! Oh, perhaps I should have said it’s the new start of the post-COVID life.

Nonetheless, the escape trip that had been planned to be relaxing was kicked off by the 4-hour lake-trapping misery. It might seem irrelevant to the topic of this article, but interestingly this unexpected interlude is strikingly similar to my 4-year Ph.D. journey so far. Starting with getting on the canoe, holding the paddle, and excitedly watching the magnificent lake view, then going through a slightly challenging but endurable voyage and arriving at the eagle nest told by the local people. Suddenly, the wind direction was switched, and the destination looked unapproachable. We kept adjusting the possible routes to go back but soon realized the theory had always lagged behind the real situation. Sometimes we were blown to a neighboring island, and within a blink, we were blown back to the eagle’s nest island again. Most of the time, we were basically circling around the same position. Seeing the sun rising and rising, I started to wonder if we could really safely go back to the shore. Luckily, I was not alone, and the cheering and collaboration between me and Brabeeba really made a difference. When the wind was strong, we tried to stabilize the canoe and made sure we were not moving backward by too much. When the wind was smaller, we turned on our turbo and dashed for as many meters as possible. When we were getting closer and closer to the shore, we suddenly realized how different the sense of distance on the water compared to what it really was. We always thought it was going to be the last five minutes of the journey and sadly realized the scenery in front of us did not really change afterward. The details of the destination finally became clear at the very last moment, and without any preparation in mind, we had already arrived at the shore.

The unexpected trap shattered the romantic illusion of living by a lake. While frantically consuming snacks in the wooden house to regain some energy, I vowed never to canoe again in my life and worried that the soreness of my muscles would ruin the rest of the vacation. However, after waking up to the birds’ songs the next morning and meditating by the lake, I couldn’t help but fall in love with the depth and spirit of nature. My muscles were not as tired as expected, and they seemed to ask where the next journey would be.

After four years of Ph.D. life, I feel like a little boy who just finished a voyage, tremblingly witnessing the majesty of the world. I still have doubts about my ability and perhaps some disappointment in the shallowness of my former self. My passion is no longer vigorous but increasingly rounded and steadfast. Where is the next journey? This will be an unstoppable question, and the certain response would be: I will keep moving forward and thriving.

Before the next journey, let me record and share some recent thoughts.

What have I done in the past year?

The pandemic has made daily life monotonous and time seems to pass by quickly. Compared to the growth and challenges of the past few years, this year feels like waiting for a feast to cook in an oven, wondering about the next dish.

As for learning, I am still not accustomed to online courses and often miss important parts. Seeing students leaving Zoom immediately after class makes me miss corridor discussions and debates in front of a blackboard. After serving as a teaching assistant for two semesters and a week of summer school, I feel like I’m missing something. I can no longer observe each student from the last row in the classroom and it’s even harder to take care of everyone during office hours. Before the pandemic, when the “flipped classroom” had started to become a trend, I thought online courses would gradually replace physical courses entirely. Not until the pandemic lockdown did I realize that real-world interactions with people are irreplaceable.

Despite this, these teaching experiences have been a great source of mental nourishment for me during the pandemic. Students’ curiosity and eagerness to learn have reminded me of the pure and original passion of studying theoretical computer science. Seeing students slowly grow and start to ask interesting questions gives me a sense of achievement and happiness that I cannot get from doing research. This makes me determined to pursue education and academics in parallel.

In terms of research, there have been several follow-up works on the two breakthrough directions from last year. However, time has flown by, and I suddenly realized that I am less excited about some of the research results I have obtained. Furthermore, I now spend much less time on my most interesting problems, let alone studying new knowledge and thinking about a long-term research agenda. Looking at the tiny amount of time left in my Ph.D. life, I have gone into another swamp of confusion, not knowing how to properly allocate my time.

There are perhaps two main ways of time allocation among the postdocs and Ph.D. students I’ve met. The first type is what I call the “greedy algorithm,” where one goes all in when there are research problems that are doable and solves every follow-up work. The second type is what I call the “idealist,” where one only spends time on his or her favorite problem(s) and does not care that much about the production and progress. Of course, most people are a mixture of the two types. But from my observation, most people who survive in the end are often those who adopt one of the extreme styles. The two styles are incomparable and give different contributions to scientific advancement. Certainly, academia needs both types of researchers, so the point is to identify which style (perhaps beyond these two) works best for you!

In addition to the above meta-level thinking in research direction and style, I’ve been pondering a lot about the essence of scientific research, the differences and similarities among fields, the weaknesses of us as humans, and these sorts of philosophical questions. Let me try to roughly summarize my fuzzy thoughts in the rest of this post.

The differences and similarities among scientific fields

Since I started studying and doing research in Physics and Neuroscience two years ago, I gradually realized that the methodology, goals, and philosophies in different fields could be very different, and sometimes even contradictory or conflicting. For example, in theoretical CS, research without solid and rigorous mathematical proof is nearly impossible to gain recognition from the field. However, people care much less about the relevance of results to the real world and practical applications. Sometimes TCS people might even say “a research being too practical is no longer doing theory”. As for theoretical physics, my superficial understanding suggests that the requirement for mathematical rigor is not absolute. A common research approach is to provide complete theoretical analysis in a simpler setting and use experiments or computer simulations to support more complicated but realistic situations. In theoretical neuroscience, even the most theoretical works I’ve ever seen still use “fuzzy math,” and the focus is usually on experimental designs and how well the theory/model explains observed phenomena.

I really like my friend Lisa’s way of visualizing the differences among scientific fields via “knowledge trees.” Mathematics and Physics are like holy giant trees, aggregating centuries of knowledge and having many sub-branches entangled with each other. Computer Science is like a binary tree, with explosive growth in recent years and many branches, but relatively few long branches like the trees of Mathematics and Physics. Biology is then like shrubbery, touching tremendous observations and questions but rarely having a unifying understanding among sub-fields.

Such differences partly stem from the development and evolution of each field and partly from the subject a field is studying. For computer scientists, thanks to the abstraction of Turing, we can purely work in a utopian realm where everything can be captured by beautiful math. But for physicists and neuroscientists, what they are facing is the complicated and mysterious nature. Consequently, it is much more challenging to mathematize, and sometimes I even doubt whether it is really possible for living science to encompass elegant mathematical theory like CS and Physics.

Recently, I have been participating in a reading group for the book This is Biology by Ernst Mayr, a giant in evolutionary biology. The book discusses the philosophy of biology, and my goal is to build up my own scientific picture and think about the possibility of theoretical and abstract study in living science! I will write a separate post on this very soon!

The importance of open-minded and communication

As a junior student and researcher in academia, it’s very difficult to understand the perspectives of other fields after just becoming accustomed to the methodology of one’s home field. Sometimes this difficulty arises purely due to a lack of understanding, for example, I still find it challenging to appreciate the importance of some breakthrough results in neuroscience even after reading neuroscience papers for two years. Other times it’s because of a different way of thinking, like how computer scientists are very used to thinking algorithmically while physicists and mathematicians place more emphasis on symmetry and harmony. If one tries to force another field to think like their field, it not only is likely to fail but could also be very offensive. So, to foster a healthier and more comfortable environment, it’s crucial to be open-minded. This doesn’t necessarily mean that one has to understand and appreciate other fields, the point is simply that there’s no single field that is superior to the others, and we should embrace the diversity in academia!

Let’s even first ignore cross-disciplinary research. Being receptive to the diverse research methodology/style is also very crucial even in our own little sub-field. In the past year, I went through a drama of offending my collaborators due to the different styles of doing research: I like to understand the high-level strategy of a mathematical proof before pinning down every step of details, while some people are more comfortable with understanding a proof line by line. These two styles are both common in theoretical CS, and two persons with different styles can even be a really good match. However, I previously thought everyone should default to my style, and hence made my collaborator with the second style have a very difficult time understanding what I’m explaining. Not until we got a chance to chat about this and tried to understand each other did we figure out a better way to collaborate.

From the language and methodology gap among scientific fields to the difference in personal styles, I realize one of the valuable but often overlooked merits of scientific research: communication. In the ideal situation, Science and traditional dogma are very different in the lack of authority, emphasis on verification, and open discussion. Though of course, this is quite idealistic, and reality (e.g., caused by competition) might disappoint me, the difference between Science and other failed Utopians is that it is, in principle, not a bad idea to improve one’s communication skills and acceptance of others.

However, when I discuss with friends about the role of communication in science, some might doubt its necessity. Their argument is that in order to make others understand and appreciate their research, they might sometimes have to sacrifice the core value or originality of their work. Some more radical arguments suggest that there’s no need to spend time writing papers, and good research should prove itself without being written properly. Firstly, I believe there’s no conflict between independence of thinking and the understandability of a work. Furthermore, it’s often the case that one gains a clearer and deeper understanding after writing the paper or explaining it to others. Secondly, in my opinion, one key difference between science and art is that science chases objectivity in its essence while art embraces diverse and subjective expositions. To achieve the ideal objectivity in science, communication then becomes a critical step, and in modern science, writing is one of the ways to do it (of course, it could be the case that in 50 years there will be a better way to communicate!).

Deep understanding vs. Clear understanding

I am not sure when I started having a stubborn pursuit of deep understanding. That is to say, no matter what I encountered, I unconsciously judged how deep a question is and looked down upon problems that I think are not deep enough. Such pursuit unwittingly affected my life, and I started to become very judgmental. I suddenly realized I had gone too far when some of my close friends and collaborators started to have no clue about what I’m talking about.

What is “deep”? Is there an objective measure to evaluate how deep a problem is? Is deep understanding a standard to evaluate how good scientific work is? After revisiting these fundamental questions, I realized that “being deep” is as subjective as something like “being interesting.” And sometimes, when used improperly, “being not deep” could be a very offensive term. Maybe my original intention was about the scientific spirit of chasing the truth. However, once this becomes a concrete measure, it could make me have my head in the clouds and even be a little cynical.

This is not to say that pursuing deep understanding is wrong. Rather, this is a term that requires more careful and humble usage. In the meantime, I found a nice proxy for deep understanding: pursuing “clear understanding.” Looking back to my school days when I got stuck in homework problems, felt frustrated doing research, or even encountered an infinite loop while handling daily chores, what’s the common theme among them? I think all of these situations more or less stem from not clearly understanding the underlying principles or processes. In daily life, we may not necessarily need to make everything clear. However, some problems might emerge (e.g., tax issues) if such laziness aggregates. And to deal with them, the best way is often to clearly figure out the underlying issue. Similar principles can apply to the scientific frontier as well: examining scientific breakthroughs, as some of them come from a burst of inspiration, while many originate from the process of clarifying an unsatisfactory old understanding. In other words, pursuing clear understanding is a realization of intellectual honesty, and perhaps an understanding would be deep once you understand it clearly enough!

Weakness of human being and ego, rationality and sensibility

Since I noticed my obsession with abstract thinking, I started having lots of discussions about “human” with my good friend Juspreet. As science brings the belief that “man can conquer nature (人定勝天)” and modern life becomes more mechanical, we unconsciously become more like rational machines/robots and forget that we are still human beings. Francis Bacon once said,

Nature, to be commanded, must be obeyed.

Francis Bacon, Novum Organum

Similarly, being human, we should humbly acknowledge our weaknesses or, in other words, our essence.

Juspreet made two observations about me: first, he noticed that I care a lot about others’ feelings (but this doesn’t mean that I’m good at observing people…) and am also easily affected by others’ behaviors. In an open and straightforward environment (e.g., the way Juspreet and I hang out or some professional collaborations), such a personality might not be a big deal because people are straightforward with each other and can solve potential problems immediately. However, in many occasions, being too straightforward might not be very welcomed. Many people tend to tolerate each other to maintain harmony on the surface and thus implicitly create some unexploded bombs. If one does not care that much about others’ feelings, these unexploded bombs might not cause too much damage. However, if one cares about others’ feelings but also likes to be straightforward, it is then very easy to get oneself into an awkward and torturing situation. In the past year, I have suffered from such personality both in life and in research collaborations.

Fortuitously, I recently reread a book that I bought a couple of years back: “The Righteous Mind: Why Good People Are Divided by Politics and Religion,” and this book surprisingly provides me many new angles to think about my personality. The author, Jonathan Haidt, is a moral/social psychologist, and this book (as well as some of his previous books) presents a brand-new framework to describe the tangle between rationality and sensibility (in the book corresponding to “intuition” and “emotion”): other than the rationality-dominance view from mainstream scientists and popular media, the author leans more towards David Hume’s idea of “rationality is the servant of emotion.” Using plenty of psychological experiments and even viewpoints from social science and evolutionary theory, Haidt brilliantly explains how our emotions affect our rational thinking and further result in conflicts on political or religious debates.

Similar concepts can be used to explain lots of unpleasant incidents and quarrels in life and research. If one harshly rejects others’ proof ideas, is that going to make people feel embarrassed? If one deletes all the contents written by collaborators, is that going to make people feel offended? If one is impatient to explain details to the other and does not try to understand the other’s lack of background, is that going to make people feel insulted? Most importantly, when these situations happen, it is of no use to explain how innocent one was. Because once the hurt on emotion has been made, it is subjective and the emotion needs to be taken care of before rational discussion.

This is then very related to Juspreet’s second observation: ego. Although I care a lot about others’ feelings and sometimes can understand why they have such reactions, in the meantime, I still find it difficult to accept people not using the way I think is better. In other words, rationally, I can understand people’s intentions, but emotionally, I cannot agree. This is exactly the difference between sympathy and empathy.

So, besides reading and communicating to understand others’ feelings, what I really need to improve is to lower the strong ego within me. I need to accept diversity from the bottom of my heart, which happens to be the great lesson I learned from biology and nature!

Epilogue

Not sure if I have been influenced by the pandemic or a novel I recently read, but I have started to look at research and daily life from different and new angles. Time flows silently but steadily, and the world is full of hustle and bustle, changing uncontrollably. Living in reality requires us to be strong and steadfast while also acknowledging the confusion and shout-outs that build up deep in our minds. To meet basic living requirements, to spend the seemingly boundless time, to release our inner voice and express ourselves, we sometimes get caught in a fast and deep swirl and lose our direction. What are your strengths and weaknesses? What style is suitable for you? What is most important to you? Perhaps, while peddling hard in a lake, it is worth stopping for a while to think about these questions.