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

Blog (English Version)

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

Click here to go back to the original version.

My Fourth Ph.D. Life

(See here for the original Mandarin version)

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

As most of the meetings this week had been cancelled to STOC, my roommate, his wife, Brabeeba, and I took a long-lost escape trip to the north. Like the quarantine had come all of a sudden, the reopen in the US was also surprisingly fast. Within a week or two, most people on the street no longer wore a mask and most indoor activities had been back to normal. 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 the normal life is 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 to be 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 arrived at the eagle night told by the local people. Suddenly, the wind direction was switched and the destination looked so 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 were blown back to the eagle nest island again. And most of the time we were basically circling around the same position. Seeing the sun rising and rising, I started to wonder if we really could 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’s 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 broke the romantic illusion of living by a lake. While crazily consuming snacks in the wood house to gain back some energy, I kept vowing I would never canoe again in my life and worried that the sourness of my muscle would destroy the rest of the vacation. However, after waking up by the birds’ songs the next morning and meditating by the lake, I could not help but fall in love with the deepness and spirit of the great nature. The muscle also was not as tired as expected and seems to ask where would be the next journey?

After four years of Ph.D. life, I’m like a little boy who just finished a voyage, tremblingly watched the majestic world. I still have some doubt on my ability, and perhaps have some disappointment on the shallowness of my previous self. The passion is no longer vigorous, but becomes increasingly rounded and steadfast. Where’s the next journey? This is going to be an unstoppable question and the certain response would be: I’ll 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 had made the daily life lack of changes as well as made the time fly extremely fast. Compared to the growth and challenges in the past few years, this year is like putting the food into an oven, waiting for the feast and thinking about what dishes will be next.

As for learning, I’m still not very used to online courses and always miss some important parts. Seeing students immediately leaving the zoom room right after a class, I started to miss the corridor discussion and debates in front of a blackboard. After being a teaching assistant for two semesters (Spectral graph theory and Complexity theory) and a week of summer school in a row, there’s always a feeling of missing something. I no longer can observe each student from the last row in the classroom and it’s even harder to take care of everyone during the office hour. Before the pandemic when the flipped classroom had started to become a business, I thought online courses were going to gradually replace physical courses completely. Not until the big lock down due to the pandemic did I finally realize the real-world interaction with people is totally irreplaceable.

Nonetheless, these teaching experiences still have served as great mental food to me during the pandemic. Students’ curiosity and eagerness to knowledge had reminded me of the pure and original passion of studying theoretical CS. Seeing students slowly growing and starting to ask interesting questions, the sense of achievement and happiness are something I cannot get from doing research and make me determined to pursue education and academics in parallel.

In terms of research, there have been several follow-up works on the two directions that had breakthroughs last year. Time had flown away within a blink after wrapping up a few papers and I suddenly realized I’m less excited about some of the research results I got. Furthermore, I now spend much less time on my most interesting problems let alone studying new knowledge and thinking of a long-term research agenda. Looking at the tiny amount of time left in my Ph.D. life, I went into another swamp of confusion, don’t 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 all-ins when there are some research problems that are doable and solves every follow-up works. The second type is what I call the idealist where one only spends time on his/her favorite problem(s) and doesn’t 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 that survive in the end are often those who adopted 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 (maybe beyond these two) works best for you!

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

The differences and similarities among scientific fields

Since I started to study and do research in Physics and Neuroscience two years ago, I gradually realized the methodology, goal, philosophy in different fields could be very very very different. Sometimes it could even be contradicting or conflicting with each other. For example, in theoretical CS, a research without solid and rigorous mathematical proof is nearly impossible to gain recognition from the field, however, people care much less on the relevance of our 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, from my superficial understanding, the requirement of mathematical rigor is actually not that absolute. A common research approach is to give a complete theoretical analysis in a simpler setting and use experiments or computer simulations to support more complicated but realistic situations. And for theoretical neuroscience, even the most theoretical works that I’ve ever seen is still in a stage of using fuzzy math and the focus is usually on experimental designs and how well the theory/model explains the observed phenomena.

I really like the way my friend Lisa to visualize the difference among scientific fields via knowledge trees: Mathematics and Physics are like holy giant trees (神木), aggregating centuries of knowledges and having many sub-branches entangling with each other. Computer Science is like a binary tree, having explosive growth in recent years and getting many branches but there are relatively few long branches like what the trees of Mathematics and Physics have. Biology is then like shrubbery, touching tremendous observations and questions but rarely having an unifying understanding among sub-fields.

Such differences were partly coming from the development and evolution of each field and partly coming from the subject a field is studying. For computer scientists, thanks to the abstraction of Turing we are able to purely work on an Utopian where everything can be captured by beautiful math. But for physicists and neuroscientists, what they are facing is the complicated and mysterious nature. As a consequence, it is much more challenging to mathematicize and sometimes I even doubt that is it really possible for living science to encompass elegant mathematical theory like CS and Physics?

Recently I’m participating a reading group for the book This is Biology by Ernst Mayr, a giant in evolutionary biology. The book talks a lot about the philosophy of biology and my goal is to build up my own scientific picture as well as thinking about the possibility of theoretical and abstract study in living science! I’ll write a separate post on this very soon!

The importance of open-minded and communication

As a junior and young student/researcher in academia, it’s very difficult to stand in the shoes of other fields after just getting used to the methodology of the home field. Sometimes it is purely due to the lack of understanding, for example, I still often find it difficult to appreciate the importance of some breakthrough results in neuroscience after reading neuroscience papers for two years. Sometimes it is because of the different way of thinking, like computer scientists are very used to thinking algorithmically while physicists and mathematicians emphasize more on symmetry and harmony. If one tries to force another field to think like his/her field, it not only is going to fail with high chances, but also could be very offensive. So to have a more healthy and comfortable environment, it is very important to be open-minded. This does not 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 had exactly gone through a drama of offending my collaborators due to the different styles of doing research: I like getting 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 be in my style by default and hence made my collaborator with the second style have a very difficult time in understanding what I’m explaining. Not until we got a chance to chat about this and tried to understand each other did we figure our 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 of verification, and open discussion. Though of course this is quite idealistic and the 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 to others.

But 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 might sometimes sacrifice the core value or originality of their works. Some more radical arguments would be there’s no need to spend time on writing papers, a good research should prove itself without being written properly. First, I believe there’s no conflict between the independence of thinking and the understandability of a work. Furthermore, it is often the case that one gets a clearer and deeper understanding after writing the paper or explaining to others. Second, in my opinion, one key difference between science and art is that science chases for 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

Not sure since when did I start to have a stubborn pursuit in deep understanding. That is to say, no matter what I encountered, I unconsciously judged how deep a question is and looked down toward the problems that I think are not deep enough. Such pursuit unwittingly affected my life in the way that I started to be very judgemental. I suddenly realized I had gone too far until some of my close friends and collaborators started to have no clue on 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 a scientific work is? After revisiting these fundamental questions, I realized “being deep” is as subjective as something like “being interesting”. And sometimes when used improperly, “being not deep” could be a very offensive word. Maybe my original intention is about the scientific spirit of chasing the truth. However, once this becomes a concrete measure, it could make me have my head in the cloud and even a little cynical.

This is not saying 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 the school days when getting stuck in homework problems, the frustration in doing research, or even the infinite loop in handling daily chores, what’s the common theme among them? I think all of these situations are more or less coming 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 issue…) once 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 those scientific breakthroughs, as some of them came from a burst of inspiration, many originated 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 clear enough!?

Weakness of human being and ego, rationality and sensibility

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

Nature, to be commanded, must be obeyed.

Francis Bacon, Novum Organum

Similarly, being a human, we should humbly acknowledge our own weakness, or to say, our essence.

Juspreet made two observations on 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 also am easily affected by others’ behaviors. In an open and straightforward environment (e.g., the way Juspreet and I hanging out or some professional collaborations), such personality might not be a big deal because people are straight to each other and hence can solve the potential problem immediately. However, in many occasions, being too straightforward might not be very welcomed. Many people would tend to tolerate each other to maintain the harmony on the surface and thus implicitly created 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’ feeling but also like to being straightforward, it is then very easy to get oneself into an awkward and torturing situation. In the past year, I have been suffered from such personality both in life and in research collaborations.

Fortuitously, I recently reread a book that I bought couple 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 toward 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 deleted all the contents written by collaborators, is that going to make people feel offended? If one was impatient to explain details to the other and did not try to understand the other’s lack of background, is that going to make people be insulted? Most importantly, when these situations happen, it is 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 better. In other words, Rationally I can understand people’s intention behind 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. To accept the diversity from the bottom of my heart, which happens to be the great lesson I learned from biology and the nature!

Epilogue

Not sure if I have been influenced by the pandemic or the novel I read recently, I started to use many different and new angles to look at research and daily life. Time flows, silently but steadily. The world is full of hustles and bustles, and changes uncontrollably. We, living in the reality, on one hand need to stay strong and steadfast and on the other hand cannot ignore the confusion and shout-out aggregated deep in our mind. To satisfy basic living requirements, to spend the seemingly boundless time, to release our inner voice and express ourselves, sometimes we fall into a fast and deep swirl and lose our direction. What’s your strength and weakness? What’s the style that is suitable for you? What’s the most important thing to you? Maybe while you are peddling hard in a lake, it is worth stopping for a while to think a little bit about these questions.

The Glass Bead Game

(See here for the original Mandarin version)

It’s quite embarrassing to admit that I had never finished reading an English book (as well as an English paper…) from the first page to the end before this year. For textbooks, it might be understandable because either the professor could only cover at most half of the materials or I just use it as a reference for specific contents. As for novels or non-fictions, I always gave up halfway through and bought a Chinese translation because my English reading speed is way too slow. This worked pretty well before the pandemic as I went back to Taiwan every year and hence can easily get books in Chinese. However, since the never-ending pandemic started, my storage of Chinese books has died out so I have no choice but to start reading English books, slowly.

I’m not a person who reads a lot. On average, I read about 10 to 20 books per year and everyday I probably just read 30 minutes to an hour before going to bed. Especially, as I have good control of myself, I won’t read more than 3 chapters per day even when I get obsessed with a novel. So for a 300-page Chinese novel, it could still take me about 2 to 3 weeks to finish. The pandemic finally forced me to seriously read an English novel. And guess how long did it take for me to finish it? Nine months for a 400-page English novel! To compare the speed of reading, my Chinese reading speed is almost 15 times faster than that of English!

This very first English novel I finished, The Glass Bead Game by Hermann Hesse, was actually originally written in German (German book title: Das Glasperlenspiel). So if I ever learn German in the future, it probably is going to take me another two three years to finish the original version of the book… But anyway, before sharing my thoughts on the book, I must say that reading English novel (too bad the original language of this book is not English) is a completely different experience compared to reading a Chinese novel. On one hand, the grammar and the sentence structure build up an exotic atmosphere. On the other hand, the word choice (although I don’t know too many vocabularies so I have to look up many words during the reading) adds up another layer of richness and texture. Let me make an analogy, translating an English novel in Chinese, is like compiling a piano sonata into a Violin version. So of course the sonata can be played beautifully even under the disguise of a violin, but no doubt there are some subtle ideas and feelings from the composer that can only be expressed on a piano .

Prologue - On the enlightenment of scientific research and some recent thoughts and reflections

After reading The Glass Bead Game, I had some brand-new reflections on scientific research. What is scientific research? Everyone probably has a very different answer to this question. Moreover, people’s comprehension might also change throughout their lifetime. To avoid misunderstanding others’ interpretation on scientific research, let me try not to give a straightforward answer to this question but instead talk about my own understanding at the different stages of my life!

My enlightening moment of science happened much later compared to most people here at Harvard. When I was a kid, my parents tried very hard to provide me with a less competitive environment and allowed me to explore different possibilities. And my hyperactive personality also naturally brought me to spend most of my time on sports and exercises. At that time, learning was simply a “citizen’s duty” to me and research was nothing more than a star in the sky that I knew existed but never really thought about it. The only impression was probably about some classmates who worked really hard on high school scientific fairs in order to get into top universities.

In the first three year of my undergraduate study, I started to get exposure to some interesting knowledge, including the beauty of mathematics, the complex of history, the profoundness of sociology, and the abundance of philosophy. The way of knowledge being taught and formed completely opens up my passion and curiosity in learning. This made me really want to stay in such an environment so that I can keep consuming these mental nutritions. But how can I stay in such an environment forever? After consulting with many people, I realized I have to “do research” to exchange for the ticket of staying in academia. However, what is doing research? To the young and naive me at that time (and probably also for most of the people), the pictures in mind are great scientists like Einstein sticking out his tongue writing alien equations on a blackboard or hustling among indescribable machines.

Nevertheless, as a computer science major, the so-called research seems to be quite different from the normal picture. Some classmates worked hard all day on trying to make a robot play soccer, some buried themselves into gigantic programming development projects, and some were always waiting for the training of their machine learning models. To me, as a person who loves abstract thinking, none of these look like the knowledge that I am interested in. Probably the only one time I found excitement was in a software engineering project where the professor recommended me learning Design Pattern to apply in a big program. I was so obsessed with the elegant object-oriented concepts in Design Pattern, however, these beautiful abstract concepts are never the leading character of a research project.

Unexpectedly, in the last year of my undergraduate study, I settled myself in doing theoretical computer science research after a huge detour. There were not so many people in Taiwan studying theoretical computer science, so there was no concrete research problem to work on and not too many people to discuss with. Nonetheless, on the bright side, such an environment provided me the freedom to swim in the ocean of knowledge. I read as many papers and books as I wanted and wrote a bunch of high quality notes. Looking back, it was really a happy and spiritually-fulfilled period of time.

Later on, I started my Ph.D. journey at Harvard and ambitiously wanted to keep learning as much as possible like a sponge. Meanwhile, I also expected myself to make new contributions in the field through my research. Years after years, I gradually realized the pure beauty of knowledge and learning that had attracted me in the very beginning is not completely the primary aim of frontier scientific research. Some people might even look down to those who spend too much time on learning rather than producing as many research papers as possible. I began to comprehend the criticism of Thomas Kuhn on the so-called Normal Science that I learned a long time ago in a class about philosophy of science. The recent reading of The Glass Bead Game was then the last straw that strikes me on my head. All these led me back to the very fundamental and basic question: what is scientific research? What is it for?

The Glass Bead Game

After reading The Glass Bead Game, that philosophical and spiritual revelation was definitely no less than the first time I learned modern mathematics back in college. After ideating for a few weeks, I still could not find a satisfying way to start the article. So I decided not to directly talk about my thoughts and feelings; instead, I’ll quote some of the paragraphs in the book (without spoiling the contents) and write some thoughts related to those paragraphs. The sentences and the page numbers come from the English translation by Richard Winston in 1969. In the Chinese version of this blog post, I also tried to further translate these paragraphs into Chinese. So if you can read Chinese, please take a look!.

The pursuit of perfection and purity

There is truth, my boy. But the doctrine you desire, absolute, perfect, dogma that alone provides wisdom, does not exist. Nor should you long for perfect doctrine, my friend. Rather, you should long for the perfection of yourself. The deity is within you, not in ideas and books. Truth is lived, not taught. Be prepared for conflicts, Joseph Knecht, I can see they have already begun.

Page 83.

As an extremely lucky person, except some little economical pressures from the family, my parents have been giving me great freedom to choose my life path according to my instinct and passion. As a consequence, my life has been filled with idealistic colors and I care very less about practical affairs. After being exposed with the knowledge from all those nicely packaged disciplines, the pursuit of perfection and purity had become even deeper in my mind. It was about the third year of my Ph.D. when I started to try out cross-disciplinary research and become aware of the huge gap between theory and reality. Especially after I dwelled into the questions in biology, I began to doubt the belief in the existence of the theory of everything. My philosophy had been seriously challenged. This felt like knowing Santa Claus is not real and realizing that the world is not as simple and beautiful as imagined.

Believing the existence of a perfect and pure doctrine is a romantic choice. Or, it is a relatively simple choice. As Nietzsche said “God is dead”, doubting one’s own religion or even abandoning it will lead to a road that is filled with fight, conflict, and confusion. But, perhaps this is the only road that goes to the real world?

The value of knowledge, life, and existence

At that time I was ambitious to work out a history of the sonata from a new point of view; but then for a while I stopped making any progress at all. I began more and more to doubt whether all these musical and historical researches had any value whatsoever, whether they were really any more aesthetic substitute for living a real life. In short, I had to pass through one of those crises in which all studies, all intellectual efforts, everything that we mean by the life of the mind, appear dubious and devalued and in which we tend to envy every peasant at the plow and every pair of lovers at evening, or every bird singing in a tree and every cicada chirping in the summer grass, because they seem to us to be living such natural, fulfilled, and happy lives. We know nothing of their troubles of course, of the elements of harshness, danger, and suffering in their lot. In brief, I had pretty well lost my equilibrium. It was far from a pleasant state; in fact it was very hard to bear.

Page 101.

This paragraph truthfully describes my life in the past year. The longer I stay in academia, the more research experience and maturity I have gained. But it is the deeper understanding of the field that gave birth to the doubt on the meaning of research. Outside the experts in the field, what’s the value of getting a few more “research results”? When I tried to be very honest in answering this question, I realized the main value seems to be making myself happy. The happiness includes the satisfaction of curiosity, the sense of achievement in solving a problem, the vanity of being recognized by others, and the usefulness of producing something.

Thinking about these questions about value is not challenging the real value of research, but rather a self-reflection of what I really want. If I will sacrifice my life, family, and health to produce a great contribution in science, is this really what I want? If so, why sometimes there is so much struggle deep in my heart? Or maybe the joy from research is no longer as strong as in the old days? Value is not an absolute measure, it adapts and changes with time and space. How to know that my own value is gradually changing and how to face it?

Doubting the meaning of learned

What was important to him were his studies, all of which now centered around the Game. Another preoccupation was, perhaps, that one question of whether the Game really was the supreme achievement of Castalia and worth devoting one's life to. For even as he was familiarizing himself with the ever more recondite mysteries of the Game's laws and potentialities, even as he became more and more at home in the labyrinths of the Archives and complex inner world of the Games' symbolism, his doubts had by no means been silenced. He had already learned by experience that faith and doubt belong together, that they govern each other like inhaling and exhaling, and that his very advances in all aspects of the Game's mirocosm naturally sharpened his eyes to all the dubiousness of the Game.

Page 134.

We talked about the “value” of knowledge in the previous paragraph. And in this one the main character starts to think about the “meaning” of what is learned. Value and meaning may sound very similar, but if you think carefully, the former is more about the feeling of objective materials and sensation while the later contains subjective spiritual and emotional attachment. For example, when you criticize the research of a scientist or the work of an artist has no value, it might deny the objective and practical value, but their research and work definitely have special meaning to them.

A thing could be very valuable, but meaningless. Take an extreme (fake) example, if a great baseball player had set up many records during his professional career and left beautiful memories within his fans. However, suppose he actually hates baseball due to the bad memory from his childhood hash training and he just played baseball for the money. Even though what he has been doing is quite valuable to his fans and the society, it is meaningless to him. Perhaps if he had other skills, we would have been much happier to be a chef rather than a baseball player!

Meaning is a much more vague concept compared to value. Meanwhile, people often pursue meaning once they have achieved a certain level of values in their life. That is to say, asking someone to do something that is valuable but meaningless to him/her could be very painful. On the other hand, if the thing is meaningful to him/her, then one would often enjoy the process a lot even without practical values. In such a case, meaning has great personal values. And from many examples of artists and even scientists, we can see that time might also change how society values something.

But not only value, meaning can also change, like in this paragraph the main character doubts deeply in his heart on what he had been studying. I found this paragraph brilliantly depicts the main character having had even more doubts after having a deeper and better understanding of the game. This is such an ultimate demonstration of intellectual honesty and woke up the anxiety in my mind. For my own field, I have enjoyed both the learning and research process very much and still feel so nowadays. However, after getting more and more exposures to other fields in the past two years, there’s some indescribable concern arose inside me (perhaps this had been ideated since this blog post). Of course, there’s not so much changes in my field and its meaning to other people should not be differed by too much. But because of my own exploration and growth, I have to start rethinking about what’s the meaning of the thing I’m working on.

The Utopian of purity and abstraction

And we go even further into the realms of pure mind, or if you prefer, pure abstraction: in our Glass Bead Game we analyze those products of the sages and artists into their components, we derive rules of style and patterns of form from them, and we operate with these abstractions as though they were building blocks. Of course all this is very fine; no one will contend otherwise. But not everyone can spend his entire life breathing, eating, and drinking nothing but abstractions. History has one great strength over the things a Waldzell tutor feels to be worthy of his interest: it deals with reality. Abstractions are fine, but I think people also have to breathe air and eat bread.

Page 279.

Recently I watched a TV series “Upload” with my roommates. It is a story about people who can upload their soul to a cloud server and live there after their death. Just from this one line description of the setup, one can already imagine lots of interesting stories and questions can be developed and the screenwriter as well as the director indeed did a very good job making the whole TV series fascinating. Suppose such technology comes up in the future, would you like to “upload” yourself and live a life without physical and physiological constraints and do whatever you like to do?

In some senses, the Castalia (a place in the book where all the game masters gather and live) in The Glass Bead Game is like a cloud server. Everyone in Castalia only needs to focus on the Game and try to be better and stronger. They don’t need to worry about other mundane and practical burdens as well as problems from the past. Similarly, some fields in our own world also more or less evolve into such s state - immersed themselves in the beauty of purity and abstraction like the Qintan in the Wei-Jin period of Chinese history.

One thing I found interesting and puzzling about this paragraph is: why does the author compare the Glass Bead Game with History? In particular, what does “it deals the reality” want to express? Compared to now and the future, history lives in the past and hence like the abstract world which is also not really existing at the moment. History studies the people and events from the past and probably the only practical value is “knowing the present from learning the past”. From this aspect, History indeed bears a lot of similarity with a pure and abstract discipline. However, the major difference between the two is that at least history did happen in reality. While abstract disciplines like math and philosophy sometimes have very practical applications, intrinsically they exist in the Utopian of purity and abstraction.

In fact the author didn’t explicitly mention “Utopian” in the book. But I purposefully call a pure and abstract world (like the Glass Bead Game in the book or math and philosophy) as an Utopian. In such an abstract world, we basically only think about the perfect side of ideas and hence in other words it is really like an escape from facing the reality. We should not forget that we in the end live in this very real world. But it’s likely to say that within ten or more years the technology can realize the setting in the TV series “Upload”, perhaps the abstraction will become the new reality?

The role in the society

These fine teachers out there are, strictly speaking, the only ones among us who are really carrying out the purpose of Castalia. Through their work alone we are repaying the nation for the many benefits we receive from it. Granted that every one of us brothers of the Order knows that our supreme and most sacred task consists in preserving the intellectual foundation of our country and our world. That foundation has proved to be a moral element of the highest efficacy, for it is nothing less than the sense of truth - on which justice is based, as well as so much else. But if we examine our real feelings, most of us would have to admit that we don't regard the welfare of the outside as well as inside our tidy Province, as the chief thing. In fact, it is not at all important to us. We are only too glad to leave it to those brave teachers out there to pay our debt to the world by their self-sacrificing work, and so more or less justify the privileges we enjoy, we Glass Bead Game players, astronomers, musicians, and mathematicians. It is part of the above-mentioned arrogance and caste spirit that we do not much care whether we earn our privileges by accomplishments. Even though our abstemious way of life is prescribed by the Order, a good many of us plume ourselves on it, as if it were a virtue we were practicing purely for its own sake instead of its being the least that we owe to the country that makes our Castalian existence possible.

Page 350.

There’s a friend once shared on Facebook after he received an award of distinguished teaching that an old professor in his department told him on his first day of being a professor: “Teaching is the core of being a professor, while research is something auxiliary and additional”. I always find this saying quite intriguing. So for a professor or a researcher in an academic institute, what’s the duty to the society? Producing top research and advising younger generations, which one is more central?

Normally, people might treat this as a binary question. Some people are good at research while some are good at teaching. Maybe a minority of them are good at both but most of the time people seem to fail on both. But if you think carefully, the core of doing research is also a process of passing on knowledge. Every (scientific) research is built on communication: At the beginning being recognized by the experts in the field, then maybe starting to have some follow-up works. Some even starts influencing other fields and some even being written into a textbook. In the end, slowly turn back to the society and flow into the river of history.

So to me, research is another form of teaching. Its foundation is still about passing on knowledge. As a member of academia, our duty to the society circulates around learning, discovery, and passing knowledge. In this paragraph, the author sharply criticizes the “Glass Bead Game players” who only focus on learning and discovery. This really resembles and satirizes the current situation in academia. But anyway, as a Ph.D. student, I probably don’t have the position to say too much. And this in the end is a personal choice in this world of survival of the fittest. Too much criticism might only lead to antipathy so I just expect myself to remember these fundamental values and meanings deeply in my heart.

Awakening and reality

I never thought of those awakenings as manifestations of a god or daimon or of some absolute truth. What gives these experiences their weight and persuasiveness is not their truth, their sublime origin, their divinity, or anything of the sort, but their reality. They are tremendously real, somewhat the way a violent physical pain or a surprising natural event, a storm or earthquake, seem to us charged with an entirely different sort of reality, presence, inexorability, from ordinary times and conditions. The gust of wind that precedes a thunderstorm, sending us into the house and almost wrenching the front door away from our hand - or a bad toothache which seems to concentrate all the tensions, sufferings, and conflicts of the world in our jaw - these are such realities. Later on we may start to question them or examine their significance, if that is our bent; but at the moment they happen they admit no doubts and are brimful of reality. My 'awakening' has a similar kind of intensified reality for me. That is why I have given it this name; at such times I really feel as if I had lain asleep or half asleep for a long time, but am now awake and clearheaded and receptive in a way I never am ordinarily.

Page 395.

I always feel that life is a journey of continued awakening and recognizing the truth and reality. Think about your first time having delicious sashimi, the first time listening to beautiful music, the first time being touched by a mathematical proof, the first time looking over the whole city from the top of a mountain. After experiencing something, the way we see the world is no longer the same. As our vision and knowledge have been expanded, it is hard to turn back to the original simple mindset. Our appetite becomes more and more difficult to satisfy, we start to be able to hear the delicate ideas in a piece of music, we pursue the extreme of abstract thinking, we yearn for traveling to every corner of the world. An awakening can be either large or small, but usually people might not be aware of it at that moment. After accumulating enough levels of awakening do we suddenly realize we are no longer the same person anymore.

Some awakening might totally change one’s value system. Like during the age of enlightenment, people walked from religion and emotion to science and rational thinking. In this confession, the main character from the book even uses vivid analogies and examples to stress the violent shock he received from the sense of reality from the awakening. After reading The Glass Bead Game, I experienced a similar awakening experience. Now that when I think about my research or things in life, I start to consider some aspects that I never had thought about before. In particular, the meaning and value toward a thing start to change. When I look back at myself a few years ago, a foreign feeling shocks me and I’m very surprised by why I care so much about certain things and why I sacrificed so much on the important ones.

Dream or real
Awake or sleep
Everlasting night, the wind gently touches
Dazzling day, the living vigorously bustles
Oh the ferryman
Where's the next harbor'?

Epilogue

What impressed me the most about The Glass Bead Game is that the author never gives a dogmatic preaching on what he really wants to say. Through the growth and life path of the main character, these ideas would naturally emerge from the reader’s heart and have a feeling that “Ah ha, he wrote out my own fuzzy feelings and thoughts!” Even in the end of the story, there’s a feeling about how the story is going to end when I was still a few pages away. The author finally uses beautiful and fluent words to end the story in a supposedly surprising but surprisingly not surprised way, like an everlasting hymn.

Back to the question in the very beginning about the meaning of scientific research to me. I guess rather than using another thousand words to elaborate, why not simply use the above six paragraphs that deeply resonate my feelings. Let the reader guess, think, and feel about my awakening moment!

(Thank Brabeeba Wang and Wei-Chung Lee for useful feedbacks in an early draft of this post!)

My Third Ph.D. Year

(Thank google translate for a first pass on the translation and thank Katherine Angier for super helpful comments on an earlier draft. See here for the original Mandarin version)

One week after the Liqiu, the heat in New England was finally (temporarily?) relieved. Maybe this year really is hotter than the previous years, or it is the never-ending quarantine makes time feel particularly slow? The sudden pandemic has changed our daily lives as well as the perception of time. Now that Autumn is approaching, suggesting the end of another school year.

Compared with the bewildering exploration in the first two years of my Ph.D., I feel more confused in the third year after settling down with some research directions and getting some results. But what I mean by confusion here may not be as negative as it originally sounds. After all, if you stopped a graduate student at Harvard campus, I believe the majority of them will also say that they are confused about what they are doing. So perhaps the more important thing is then to know what you are confused about? In my case, I mainly doubted my own ability in the first two years of my Ph.D. But now that I’ve crossed the middle line of my Ph.D., it is “what research direction (or even life direction) I want to pursue” that has been constantly mulled over in my mind.

But anyway, before any serious discussion, let’s review what happened this year!

What I’ve done in the past year?

At around this time of last year, I decided to invest more time to study and explore theoretical neuroscience. By some funny coincidences, I started to collaborate with my best friend Brabeeba, a Ph.D. student at MIT. After countless discussion (and debate) in MIT’s student cafeteria, Harvard’s dorm, and even Boston Symphony Orchestra, we successfully solved the research problem we were looking at: giving the first convergence rate analysis for a biologically-plausible learning rule (link). The techniques we developed from that work also brought us to a cute follow-up work (link).

This close collaboration experience with Brabeeba not only brought me more confidence in doing independent research (because this work was completely done by ourselves without any guidance by professors), but also taught me a lot on how to work with other people. Brabeeba and I are very different in research styles to the extent that we are almost completely complementary to each other. On the bright side, such complementation can push the research progress swiftly. Whenever I got stuck, Brabeeba could always come up with some new ideas to circumvent, and whenever he felt that the problem comes to a dead end, it was me to find a way out. However, the difference between us could also bring up undesirable conflicts. Especially when it comes to dividing opinions on research direction or the presentation of writing, we debate all the times. To be honest, sometimes debate is a frustrating process, especially when the other person is your friend and/or your collaborator. But if you changed an angle, as long as the debate is healthy (meaning that no negative words etc.) actually it is very fortunate to have a good and straightforward communication with someone. This helps spotting mistake and ignorance and also provides diversity in the discussion. In the case of working with Brabeeba, in the end we can usually turned the disagreement into a positive force into the research. Also, it is very enjoyable to have a collaborator being one of your best friends!

As for my main research focus in complexity theory, although frustratingly and unexpectedly there is still no progress in most of the directions I’m interested in, luckily one line of works finally has some non-trivial progresses. The starting point is a simple question: how well can you approximate the maximum directed cut of a directed graph (Max-DICUT) with only logarithmic space (when the edges are given in a 1-pass stream)? ( )

Approximating Max-DICUT in the streaming model:

Let $G=(V,E)$ be an input directed graph. A dicut of $G$ is a partition of the vertex set $V=V_{in}\cup V_{out}$ and the value of this dicut is the number of edges going from $V_{out}$ to $V_{in}$ divided by the total number of edges.

The streaming algorithm receives the edge of $G$ in a stream (i.e., edges in $E$ are of the form $i\to j$ for some $i,j\in V$). The streaming algorithm only has logarithmic (in the number of vertices) space. We say the streaming algorithm gives an $\alpha$-approximation for some $\alpha\in[0,1]$ if it outputs a value $v\in[0,1]$ such that the following two criteria holds with good probability: (i) there exists a dicut with value at least $v$ and (ii) $v\geq\alpha\cdot v^*$ where $v^*$ is the maximum dicut value of $G$.

The figure on the left is an input directed graph. But in the streaming model, you only receive edges one by one and do not have the space to store every edges. The goal is to partition the vertex set into two parts that maximizes the number of edges going from one side to the other. In this example, see the figure on the right, every edges go from the black vertex set to the red vertex set. The goal of the streaming algorithm is to give an approximation to the maximum dicut value with limited amount of space and a single pass of input.

The trivial random sampling algorithm gives (1/4)-approximation ( ) while a previous work finds a (2/5)-approximation using a more clever idea. On the hardness side, the best known previous impossibility result only ruled out (1/2)-approximation. Namely, there is a gap between 2/5 and 1/2 in our understanding. In the collaboration with Santhoshini and Sasha, we found that, surprisingly, neither 2/5 nor 1/2 is the true answer: the optimal approximation ratio for Max-DICUT is 4/9. Through related technologies, we thoroughly analyzed the best approximation factor of boolean 2CSP under the streaming model (link)! After Madhu joining us in the beginning of the summer, we have been making significant progress along the further direction (Update: link to this follow-up work).

The (1/4)-approximation algorithm for Max-DICUT: Note that if we assign each vertex to be either black or red with equal probability, then each edge is a cut edge with probability 1/4. Namely, for a random dicut, the expected cut value is 1/4. Hence, then algorithm can simply output 1/4 knowing that (i) there exists a dicut with such dicut value and (ii) the output value is at least 1/4 of the maximum dicut value (because the dicut value is at most 1).

Finally, in the collaboration with Boaz and Xun, we tried to challenge Google’s quantum supremacy experiment. At first, Boaz and I had a simple classical algorithm, but the analysis was not very satisfying. Xun, a post doc in the theoretical physics department at Harvard, heard that we are working on this problem and introduced the tensor network technique (which is a very common tool in theoretical physics) to us. It turns out that tensor networks can directly give a rigorous analysis for the algorithm (link).

In the ongoing follow-up project, due to some fundamental obstacles in the theoretical analysis, we partly use theory and partly use numerics to demonstrate the performance of our algorithm. This kind of research methodology is very rare in theoretical computer science but is very typical in theoretical physics. In the past, I always felt that if the result cannot be rigorously demonstrated in mathematics from the beginning to the end then it does not count as a theoretical research. However, after intensively working with Xun this time, I gradually started to appreciate this kind of physic-style research methodology. Sometimes, a theoretical research with a bunch of assumptions might not provide more insights than a research with part of rigorous mathematics and part of experiments/simulations. But of course this depends on what the research problem is. If it is a fundamental theoretical and mathematical problem, the requirement for mathematical rigor must of course be 100%. However, for more practical or interdisciplinary problems, finding a beautiful balance between theory and experiment may be able to provide better insights.

New confusion?

This year, I have done researches in three very different directions and fortunately have achieved some partial results. These experiences have built up confidence in myself, but what immediately followed was thinking about my future direction. First, how to allocate my time and how to prioritize these different directions. Second, what kind of research do I appreciate and want to pursue. Although the problems in complexity theory are indeed very attractive to me, they sometimes also give me a sense of emptiness like playing intellectual games. This may be an unavoidable contradiction/paradox of pure theoretical research. On one hand, if you only look at the big problem without taking small steps, you may be stepping around at the same place forever; on the other hand, if you spend all your time on small incremental things, you might never touch the real fundamental problem. However, keep worrying and being stuck in this paradox is not going to help. I guess what I can do is to reflect on this issue regularly. What is the complexity theory for me? Is it an arena to prove my intellectual power? Or is it carrying a sense of mission to solve fundamental problems?

Therefore, at the beginning of the year, I started to have the idea of ​pursuing another Ph.D. (in Algebraic Geometry or related fields) in pure mathematics, mainly because after learning more mathematics, I deeply felt that I’m just touching the surface of real mathematics. Furthermore, much of the deep mathematics has not been (seriously) considered and applied to complexity theory. Also, learning these mathematics requires the right “language”. If I stayed in the current path, I will not have the opportunity to learn these languages ​​well. It’s like it is (almost) impossible to learn English well if you are always in a non-English native environment. But having said that, pursuing a Ph.D. in mathematics is just one of the possible ways to achieve the goal, maybe there is another better way? Anyway, it’s too early to decide. I can wait until this time next year to worry about it…

Facing the future

People are always changing. This is probably my biggest awakening in the past few years. The changes can be in the ability, vision or even in personality, and values. This tells us that what we think we want in the future at this moment may not necessarily be what we really want in the future. In my case, it’s quite funny in retrospect that the reason why I went to academia was not because I like doing research (after all, compared with most people, I started to do research relatively late), but because I love learning new things. At first glance, the academic road seems to provide a life style of life-long learning that can make me happy. Fortunately, after many years, I also found myself enjoying the feeling of exploring the unknown in research. In particular, the final results of several projects were very different from what I expected at the beginning, which made me deeply attracted by the mysterious nature of doing research. This is even more true in the research direction. A year ago, I couldn’t expect that I would be working on these research problems that I mentioned above. Similarly, I believe it is impossible to predict what I will be doing a year later.

A few weeks ago, during a walking meeting with Boaz, I told him that I had recently encountered a career crisis: I don’t know which direction to go, and I don’t know where I will be going to in the next five or ten years. Boaz’s advice was simple, but it was an enlightening moment to me. He told me to just think about what I’m going to do in the next year! Maybe it’s because there are too many people’s examples to look at before the Ph.D., so I can always plan my future plans in advance. However, when it comes to the stage of independent research, everyone must create their own path. Maybe some people can see the development in the next few years, but in most cases the future steps are highly depending on the immediate next step. In the end, everyone is changing, and the world is also changing (e.g., the sudden pandemic), so in addition to be bothered by the plan for long-term future, a very important ability is to find a good direction in each moment and work as hard as possible. This is probably also true for other life topics other than doing research.

My friends always told me don’t overthink. Indeed, thinking less may make myself less annoyed and have a happier life. But for me at least, thinking more and deeper often makes me more aware of what I really want. While we all want to live happily, but what makes oneself happy is sometimes not that obvious. Maybe the answer (if there’s any) is hidden in the confusion by wild thoughts!?

My Second Ph.D. Year

In the blink of an eye, my second year at Harvard had come to an end. Now the summer is in its half way, and soon I’m going to cross the middle line of my Ph.D. life. Compared to two years ago, I perhaps have made some progress and improvement, yet I still fell short of what I had expected of myself. During the CCC (Computational Complexity Conference) this summer, my friend Lijie gave me lots of his thoughts and advice. Although those might not completely applicable to me, it indeed reminds me to rethink my future plan and direction for the rest of the time.

What have I done in the past year?

In retrospect, this was a really frustrating year. The drama in life influenced my focus and time spent on research. Meanwhile, the choice in research direction was also not very ideal. The results in both research and learning seem to be below the bar.

This year I have been mainly focusing on algebraic complexity, in particular, matrix rigidity and border Waring rank. The former is a research program that studies a combinatorial problem (i.e., circuit lower bound) in an algebraic setting. The ultimate goal is to (explicitly) construct a matrix that is far away from low rank matrices in to $\ell_0$ norm. This will imply super-linear lower bound for logarithmic depth circuits, which will be a breakthrough in our field. I really the idea of matrix rigidity because it turns a seemingly complicated and arbitrary structure (i.e., circuits) into an algebraic problem that is much more convenient to think about. Nevertheless, after almost 50 years since its conceptualization, there have been very limited progresses in matrix rigidity. In the past year, my collaborator Sasha and I have tried multiple old and new approaches to attack the problem and even lowered the goal. However, it always feels that we are just paddling on the surface of a bottomless ocean. As for the other line of research about border Waring rank, initially I just found the math to be interesting and then spent a semester learning representation theory in order to understand the paper. But once I finally understood what’s going on in the paper, I further realized that more math (e.g., lie algebra, algebraic geometry etc.) are needed for me to make some real contributions to the problem.

Looking back, I seemed to pick and dig into a research problem simply depending on my interest, and neglect whether me or the people around me have the ability to tackle the problem. I know we were always told to try our best and don’t underestimate ourselves. But in terms of pursuing frontier research, now I believe it is very important (and sometimes necessary) to arm yourself with enough gears and surround yourself with the right resource and experts. Like what Lijie asked me: “Why should this problem be solved by you?”. Other than having more time to think about the problem, what’s the strength I have over those experts in the field?

Positioning myself

So maybe this goes back to a basic but important question: what’s my own position in the field (or even the world)? Every researcher has their own strengths and weaknesses. Some excel in high-level intuition while some are skillful in complicated calculation. Some know various math tools while some are aware of the methodologies in different fields. And of course some people may also like me not be good at any specific thing… But anyway, I guess it is very normal for a Ph.D. student to feel that he/she is not good at anything. However, this should not be the case after graduation. One has to be the top person in the world in at least one skill to survive in academia. So then this boils down to the next important question: what skill do I want to cultivate for the rest of my Ph.D. and how?

In my case, I’ve always expected myself to be a broad-minded person (in TCS, math, or even in whole academic fields) and in the meantime specialize in a few small directions. So far it seems that I’m not doing a very good job along either axis. On the broad side, I might get exposed to a wide variety of subjects without significant internalization. For many things, I’m still in the level of “having heard the jargon/terminology before but don’t yet have the ability to have a meaningful conversation on them”. On the deep side, I really want to specialize in arithmetic circuits and boolean circuits. But I’m currently still in the situation in which “I know many important results and the key intuitions, but I’m not yet be able to fluently jump between different concepts and let alone ask interesting new questions”.

So in the end, I’ve always vaguely positioned myself in certain directions. The problem is that I didn’t push hard on myself toward these directions. I’m sometimes too lazy and easily get distracted by other stuffs and hence deviate from the main line. As there is not so much time left, I should start carefully think about how to push myself back to the road I want.

Next step

It is crucial to balance the time allocated to self development and a specific research problem. So one has to think carefully before investing a huge amount of time. Do you really like this research problem? What’s the meaning of this research to you? Do you think you are ready to do it right now? The two directions that I’ve been working on in the past year seem to be too specific and I kind of lose sight of the big picture. In the meantime, I’m also not very ready from a technical point of view.

So given that I really want to specialize in arithmetic circuits and boolean circuits, the key problems like lower bounds and derandomization are there and there are a few different circuit models that have their own frontier and barrier. For now, I only have a vague sense of the state-of-the-art results in most settings but don’t really have a crystal-clear understanding of what’s the bottleneck and what’s the potential breakout point. So the next next step for me is quite obvious: read more, think more, and internalize all this knowledge and build my own library. Really hope that I can pick up my good old habit of keeping notes rather than having blurry concepts in my mind.

In addition, mental stability is also important. In particular, TCS is a field that really stresses out people where smart people are everywhere and the field moves very fast. One needs to find a way to make oneself being less influenced and keep moving forward. And more importantly, positioning oneself and don’t isolate from the others. Oh god, sometimes I really feel choosing this route is really self-torture. Nevertheless, the sense of fulfillment and satisfaction are also extraordinary. There’s only one shot in our lifetime, don’t leave any backdoor for ourself and keep striving!