$ \newcommand{\undefined}{} \newcommand{\hfill}{} \newcommand{\qedhere}{\square} \newcommand{\qed}{\square} \newcommand{\ensuremath}[1]{#1} \newcommand{\bit}{\{0,1\}} \newcommand{\Bit}{\{-1,1\}} \newcommand{\Stab}{\mathbf{Stab}} \newcommand{\NS}{\mathbf{NS}} \newcommand{\ba}{\mathbf{a}} \newcommand{\bc}{\mathbf{c}} \newcommand{\bd}{\mathbf{d}} \newcommand{\be}{\mathbf{e}} \newcommand{\bh}{\mathbf{h}} \newcommand{\br}{\mathbf{r}} \newcommand{\bs}{\mathbf{s}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\Var}{\mathbf{Var}} \newcommand{\dist}{\text{dist}} \newcommand{\norm}[1]{\\|#1\\|} \newcommand{\etal} \newcommand{\ie} \newcommand{\eg} \newcommand{\cf} \newcommand{\rank}{\text{rank}} \newcommand{\tr}{\text{tr}} \newcommand{\mor}{\text{Mor}} \newcommand{\hom}{\text{Hom}} \newcommand{\id}{\text{id}} \newcommand{\obj}{\text{obj}} \newcommand{\pr}{\text{pr}} \newcommand{\ker}{\text{ker}} \newcommand{\coker}{\text{coker}} \newcommand{\im}{\text{im}} \newcommand{\vol}{\text{vol}} \newcommand{\disc}{\text{disc}} \newcommand{\bbA}{\mathbb A} \newcommand{\bbB}{\mathbb B} \newcommand{\bbC}{\mathbb C} \newcommand{\bbD}{\mathbb D} \newcommand{\bbE}{\mathbb E} \newcommand{\bbF}{\mathbb F} \newcommand{\bbG}{\mathbb G} \newcommand{\bbH}{\mathbb H} \newcommand{\bbI}{\mathbb I} \newcommand{\bbJ}{\mathbb J} \newcommand{\bbK}{\mathbb K} \newcommand{\bbL}{\mathbb L} \newcommand{\bbM}{\mathbb M} \newcommand{\bbN}{\mathbb N} \newcommand{\bbO}{\mathbb O} \newcommand{\bbP}{\mathbb P} \newcommand{\bbQ}{\mathbb Q} \newcommand{\bbR}{\mathbb R} \newcommand{\bbS}{\mathbb S} \newcommand{\bbT}{\mathbb T} \newcommand{\bbU}{\mathbb U} \newcommand{\bbV}{\mathbb V} \newcommand{\bbW}{\mathbb W} \newcommand{\bbX}{\mathbb X} \newcommand{\bbY}{\mathbb Y} \newcommand{\bbZ}{\mathbb Z} \newcommand{\sA}{\mathscr A} \newcommand{\sB}{\mathscr B} \newcommand{\sC}{\mathscr C} \newcommand{\sD}{\mathscr D} \newcommand{\sE}{\mathscr E} \newcommand{\sF}{\mathscr F} \newcommand{\sG}{\mathscr G} \newcommand{\sH}{\mathscr H} \newcommand{\sI}{\mathscr I} \newcommand{\sJ}{\mathscr J} \newcommand{\sK}{\mathscr K} \newcommand{\sL}{\mathscr L} \newcommand{\sM}{\mathscr M} \newcommand{\sN}{\mathscr N} \newcommand{\sO}{\mathscr O} \newcommand{\sP}{\mathscr P} \newcommand{\sQ}{\mathscr Q} \newcommand{\sR}{\mathscr R} \newcommand{\sS}{\mathscr S} \newcommand{\sT}{\mathscr T} \newcommand{\sU}{\mathscr U} \newcommand{\sV}{\mathscr V} \newcommand{\sW}{\mathscr W} \newcommand{\sX}{\mathscr X} \newcommand{\sY}{\mathscr Y} \newcommand{\sZ}{\mathscr Z} \newcommand{\sfA}{\mathsf A} \newcommand{\sfB}{\mathsf B} \newcommand{\sfC}{\mathsf C} \newcommand{\sfD}{\mathsf D} \newcommand{\sfE}{\mathsf E} \newcommand{\sfF}{\mathsf F} \newcommand{\sfG}{\mathsf G} \newcommand{\sfH}{\mathsf H} \newcommand{\sfI}{\mathsf I} \newcommand{\sfJ}{\mathsf J} \newcommand{\sfK}{\mathsf K} \newcommand{\sfL}{\mathsf L} \newcommand{\sfM}{\mathsf M} \newcommand{\sfN}{\mathsf N} \newcommand{\sfO}{\mathsf O} \newcommand{\sfP}{\mathsf P} \newcommand{\sfQ}{\mathsf Q} \newcommand{\sfR}{\mathsf R} \newcommand{\sfS}{\mathsf S} \newcommand{\sfT}{\mathsf T} \newcommand{\sfU}{\mathsf U} \newcommand{\sfV}{\mathsf V} \newcommand{\sfW}{\mathsf W} \newcommand{\sfX}{\mathsf X} \newcommand{\sfY}{\mathsf Y} \newcommand{\sfZ}{\mathsf Z} \newcommand{\cA}{\mathcal A} \newcommand{\cB}{\mathcal B} \newcommand{\cC}{\mathcal C} \newcommand{\cD}{\mathcal D} \newcommand{\cE}{\mathcal E} \newcommand{\cF}{\mathcal F} \newcommand{\cG}{\mathcal G} \newcommand{\cH}{\mathcal H} \newcommand{\cI}{\mathcal I} \newcommand{\cJ}{\mathcal J} \newcommand{\cK}{\mathcal K} \newcommand{\cL}{\mathcal L} \newcommand{\cM}{\mathcal M} \newcommand{\cN}{\mathcal N} \newcommand{\cO}{\mathcal O} \newcommand{\cP}{\mathcal P} \newcommand{\cQ}{\mathcal Q} \newcommand{\cR}{\mathcal R} \newcommand{\cS}{\mathcal S} \newcommand{\cT}{\mathcal T} \newcommand{\cU}{\mathcal U} \newcommand{\cV}{\mathcal V} \newcommand{\cW}{\mathcal W} \newcommand{\cX}{\mathcal X} \newcommand{\cY}{\mathcal Y} \newcommand{\cZ}{\mathcal Z} \newcommand{\bfA}{\mathbf A} \newcommand{\bfB}{\mathbf B} \newcommand{\bfC}{\mathbf C} \newcommand{\bfD}{\mathbf D} \newcommand{\bfE}{\mathbf E} \newcommand{\bfF}{\mathbf F} \newcommand{\bfG}{\mathbf G} \newcommand{\bfH}{\mathbf H} \newcommand{\bfI}{\mathbf I} \newcommand{\bfJ}{\mathbf J} \newcommand{\bfK}{\mathbf K} \newcommand{\bfL}{\mathbf L} \newcommand{\bfM}{\mathbf M} \newcommand{\bfN}{\mathbf N} \newcommand{\bfO}{\mathbf O} \newcommand{\bfP}{\mathbf P} \newcommand{\bfQ}{\mathbf Q} \newcommand{\bfR}{\mathbf R} \newcommand{\bfS}{\mathbf S} \newcommand{\bfT}{\mathbf T} \newcommand{\bfU}{\mathbf U} \newcommand{\bfV}{\mathbf V} \newcommand{\bfW}{\mathbf W} \newcommand{\bfX}{\mathbf X} \newcommand{\bfY}{\mathbf Y} \newcommand{\bfZ}{\mathbf Z} \newcommand{\rmA}{\mathrm A} \newcommand{\rmB}{\mathrm B} \newcommand{\rmC}{\mathrm C} \newcommand{\rmD}{\mathrm D} \newcommand{\rmE}{\mathrm E} \newcommand{\rmF}{\mathrm F} \newcommand{\rmG}{\mathrm G} \newcommand{\rmH}{\mathrm H} \newcommand{\rmI}{\mathrm I} \newcommand{\rmJ}{\mathrm J} \newcommand{\rmK}{\mathrm K} \newcommand{\rmL}{\mathrm L} \newcommand{\rmM}{\mathrm M} \newcommand{\rmN}{\mathrm N} \newcommand{\rmO}{\mathrm O} \newcommand{\rmP}{\mathrm P} \newcommand{\rmQ}{\mathrm Q} \newcommand{\rmR}{\mathrm R} \newcommand{\rmS}{\mathrm S} \newcommand{\rmT}{\mathrm T} \newcommand{\rmU}{\mathrm U} \newcommand{\rmV}{\mathrm V} \newcommand{\rmW}{\mathrm W} \newcommand{\rmX}{\mathrm X} \newcommand{\rmY}{\mathrm Y} \newcommand{\rmZ}{\mathrm Z} \newcommand{\bb}{\mathbf{b}} \newcommand{\bv}{\mathbf{v}} \newcommand{\bw}{\mathbf{w}} \newcommand{\bx}{\mathbf{x}} \newcommand{\by}{\mathbf{y}} \newcommand{\bz}{\mathbf{z}} \newcommand{\paren}[1]{( #1 )} \newcommand{\Paren}[1]{\left( #1 \right)} \newcommand{\bigparen}[1]{\bigl( #1 \bigr)} \newcommand{\Bigparen}[1]{\Bigl( #1 \Bigr)} \newcommand{\biggparen}[1]{\biggl( #1 \biggr)} \newcommand{\Biggparen}[1]{\Biggl( #1 \Biggr)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\Abs}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigabs}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigabs}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggabs}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggabs}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\card}[1]{\left| #1 \right|} \newcommand{\Card}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\Norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert} \newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert} \newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert} \newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\Iprod}[1]{\left\langle #1 \right\rangle} \newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle} \newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle} \newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle} \newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace} \newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace} \newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace} \newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace} \newcommand{\bracket}[1]{\lbrack #1 \rbrack} \newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack} \newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack} \newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack} \newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack} \newcommand{\ucorner}[1]{\ulcorner #1 \urcorner} \newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner} \newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner} \newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner} \newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner} \newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil} \newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil} \newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil} \newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor} \newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor} \newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor} \newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor} \newcommand{\lcorner}[1]{\llcorner #1 \lrcorner} \newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner} \newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner} \newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner} \newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner} \newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner} \newcommand{\ket}[1]{| #1 \rangle} \newcommand{\bra}[1]{\langle #1 |} \newcommand{\braket}[2]{\langle #1 | #2 \rangle} \newcommand{\ketbra}[1]{| #1 \rangle\langle #1 |} \newcommand{\e}{\varepsilon} \newcommand{\eps}{\varepsilon} \newcommand{\from}{\colon} \newcommand{\super}[2]{#1^{(#2)}} \newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}} \newcommand{\tensor}{\otimes} \newcommand{\eset}{\emptyset} \newcommand{\sse}{\subseteq} \newcommand{\sst}{\substack} \newcommand{\ot}{\otimes} \newcommand{\Esst}[1]{\bbE_{\substack{#1}}} \newcommand{\vbig}{\vphantom{\bigoplus}} \newcommand{\seteq}{\mathrel{\mathop:}=} \newcommand{\defeq}{\stackrel{\mathrm{def}}=} \newcommand{\Mid}{\mathrel{}\middle|\mathrel{}} \newcommand{\Ind}{\mathbf 1} \newcommand{\bits}{\{0,1\}} \newcommand{\sbits}{\{\pm 1\}} \newcommand{\R}{\mathbb R} \newcommand{\Rnn}{\R_{\ge 0}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\C}{\mathbb C} \newcommand{\A}{\mathbb A} \newcommand{\Real}{\mathbb R} \newcommand{\mper}{\,.} \newcommand{\mcom}{\,,} \DeclareMathOperator{\Id}{Id} \DeclareMathOperator{\cone}{cone} \DeclareMathOperator{\vol}{vol} \DeclareMathOperator{\val}{val} \DeclareMathOperator{\opt}{opt} \DeclareMathOperator{\Opt}{Opt} \DeclareMathOperator{\Val}{Val} \DeclareMathOperator{\LP}{LP} \DeclareMathOperator{\SDP}{SDP} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\Inf}{Inf} \DeclareMathOperator{\size}{size} \DeclareMathOperator{\poly}{poly} \DeclareMathOperator{\polylog}{polylog} \DeclareMathOperator{\min}{min} \DeclareMathOperator{\max}{max} \DeclareMathOperator{\argmax}{arg\,max} \DeclareMathOperator{\argmin}{arg\,min} \DeclareMathOperator{\qpoly}{qpoly} \DeclareMathOperator{\qqpoly}{qqpoly} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\Conv}{Conv} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\perm}{perm} \DeclareMathOperator{\mspan}{span} \DeclareMathOperator{\mrank}{rank} \DeclareMathOperator{\E}{\mathbb E} \DeclareMathOperator{\pE}{\tilde{\mathbb E}} \DeclareMathOperator{\Pr}{\mathbb P} \DeclareMathOperator{\Span}{Span} \DeclareMathOperator{\Cone}{Cone} \DeclareMathOperator{\junta}{junta} \DeclareMathOperator{\NSS}{NSS} \DeclareMathOperator{\SA}{SA} \DeclareMathOperator{\SOS}{SOS} \DeclareMathOperator{\Stab}{\mathbf Stab} \DeclareMathOperator{\Det}{\textbf{Det}} \DeclareMathOperator{\Perm}{\textbf{Perm}} \DeclareMathOperator{\Sym}{\textbf{Sym}} \DeclareMathOperator{\Pow}{\textbf{Pow}} \DeclareMathOperator{\Gal}{\textbf{Gal}} \DeclareMathOperator{\Aut}{\textbf{Aut}} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\cE}{\mathcal{E}} \newcommand{\E}{\mathbb{E}} \newcommand{\pE}{\tilde{\mathbb{E}}} \newcommand{\N}{\mathbb{N}} \renewcommand{\P}{\mathcal{P}} \notag $
$ \newcommand{\sleq}{\ensuremath{\preceq}} \newcommand{\sgeq}{\ensuremath{\succeq}} \newcommand{\diag}{\ensuremath{\mathrm{diag}}} \newcommand{\support}{\ensuremath{\mathrm{support}}} \newcommand{\zo}{\ensuremath{\{0,1\}}} \newcommand{\pmo}{\ensuremath{\{\pm 1\}}} \newcommand{\uppersos}{\ensuremath{\overline{\mathrm{sos}}}} \newcommand{\lambdamax}{\ensuremath{\lambda_{\mathrm{max}}}} \newcommand{\rank}{\ensuremath{\mathrm{rank}}} \newcommand{\Mslow}{\ensuremath{M_{\mathrm{slow}}}} \newcommand{\Mfast}{\ensuremath{M_{\mathrm{fast}}}} \newcommand{\Mdiag}{\ensuremath{M_{\mathrm{diag}}}} \newcommand{\Mcross}{\ensuremath{M_{\mathrm{cross}}}} \newcommand{\eqdef}{\ensuremath{ =^{def}}} \newcommand{\threshold}{\ensuremath{\mathrm{threshold}}} \newcommand{\vbls}{\ensuremath{\mathrm{vbls}}} \newcommand{\cons}{\ensuremath{\mathrm{cons}}} \newcommand{\edges}{\ensuremath{\mathrm{edges}}} \newcommand{\cl}{\ensuremath{\mathrm{cl}}} \newcommand{\xor}{\ensuremath{\oplus}} \newcommand{\1}{\ensuremath{\mathrm{1}}} \notag $
$ \newcommand{\transpose}[1]{\ensuremath{#1{}^{\mkern-2mu\intercal}}} \newcommand{\dyad}[1]{\ensuremath{#1#1{}^{\mkern-2mu\intercal}}} \newcommand{\nchoose}[1]{\ensuremath} \newcommand{\generated}[1]{\ensuremath{\langle #1 \rangle}} \notag $
$ \newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}} \newcommand{\R} % real numbers \newcommand{\N}} % natural numbers \newcommand{\Z} % integers \newcommand{\F} % a field \newcommand{\Q} % the rationals \newcommand{\C}{\mathbb{C}} % the complexes \newcommand{\poly}} \newcommand{\polylog}} \newcommand{\loglog}}} \newcommand{\zo}{\{0,1\}} \newcommand{\suchthat} \newcommand{\pr}[1]{\Pr\left[#1\right]} \newcommand{\deffont}{\em} \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}} \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance \newcommand{\xor}{\oplus} \newcommand{\GF}{\mathrm{GF}} \newcommand{\eps}{\varepsilon} \notag $
$ \newcommand{\class}[1]{\mathbf{#1}} \newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements \newcommand{\BPP}{\class{BPP}} \newcommand{\NP}{\class{NP}} \newcommand{\RP}{\class{RP}} \newcommand{\coRP}{\coclass{RP}} \newcommand{\ZPP}{\class{ZPP}} \newcommand{\BQP}{\class{BQP}} \newcommand{\FP}{\class{FP}} \newcommand{\QP}{\class{QuasiP}} \newcommand{\VF}{\class{VF}} \newcommand{\VBP}{\class{VBP}} \newcommand{\VP}{\class{VP}} \newcommand{\VNP}{\class{VNP}} \newcommand{\RNC}{\class{RNC}} \newcommand{\RL}{\class{RL}} \newcommand{\BPL}{\class{BPL}} \newcommand{\coRL}{\coclass{RL}} \newcommand{\IP}{\class{IP}} \newcommand{\AM}{\class{AM}} \newcommand{\MA}{\class{MA}} \newcommand{\QMA}{\class{QMA}} \newcommand{\SBP}{\class{SBP}} \newcommand{\coAM}{\class{coAM}} \newcommand{\coMA}{\class{coMA}} \renewcommand{\P}{\class{P}} \newcommand\prBPP{\class{prBPP}} \newcommand\prRP{\class{prRP}} \newcommand\prP{\class{prP}} \newcommand{\Ppoly}{\class{P/poly}} \newcommand{\NPpoly}{\class{NP/poly}} \newcommand{\coNPpoly}{\class{coNP/poly}} \newcommand{\DTIME}{\class{DTIME}} \newcommand{\TIME}{\class{TIME}} \newcommand{\SIZE}{\class{SIZE}} \newcommand{\SPACE}{\class{SPACE}} \newcommand{\ETIME}{\class{E}} \newcommand{\BPTIME}{\class{BPTIME}} \newcommand{\RPTIME}{\class{RPTIME}} \newcommand{\ZPTIME}{\class{ZPTIME}} \newcommand{\EXP}{\class{EXP}} \newcommand{\ZPEXP}{\class{ZPEXP}} \newcommand{\RPEXP}{\class{RPEXP}} \newcommand{\BPEXP}{\class{BPEXP}} \newcommand{\SUBEXP}{\class{SUBEXP}} \newcommand{\NTIME}{\class{NTIME}} \newcommand{\NL}{\class{NL}} \renewcommand{\L}{\class{L}} \newcommand{\NQP}{\class{NQP}} \newcommand{\NEXP}{\class{NEXP}} \newcommand{\coNEXP}{\coclass{NEXP}} \newcommand{\NPSPACE}{\class{NPSPACE}} \newcommand{\PSPACE}{\class{PSPACE}} \newcommand{\NSPACE}{\class{NSPACE}} \newcommand{\coNSPACE}{\coclass{NSPACE}} \newcommand{\coL}{\coclass{L}} \newcommand{\coP}{\coclass{P}} \newcommand{\coNP}{\coclass{NP}} \newcommand{\coNL}{\coclass{NL}} \newcommand{\coNPSPACE}{\coclass{NPSPACE}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\LINSPACE}{\class{LINSPACE}} \newcommand{\qP}{\class{\tilde{P}}} \newcommand{\PH}{\class{PH}} \newcommand{\EXPSPACE}{\class{EXPSPACE}} \newcommand{\SigmaTIME}[1]{\class{\Sigma_{#1}TIME}} \newcommand{\PiTIME}[1]{\class{\Pi_{#1}TIME}} \newcommand{\SigmaP}[1]{\class{\Sigma_{#1}P}} \newcommand{\PiP}[1]{\class{\Pi_{#1}P}} \newcommand{\DeltaP}[1]{\class{\Delta_{#1}P}} \newcommand{\ATIME}{\class{ATIME}} \newcommand{\ASPACE}{\class{ASPACE}} \newcommand{\AP}{\class{AP}} \newcommand{\AL}{\class{AL}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\VNC}[1]{\class{VNC^{#1}}} \newcommand{\NC}[1]{\class{NC^{#1}}} \newcommand{\AC}[1]{\class{AC^{#1}}} \newcommand{\ACC}[1]{\class{ACC^{#1}}} \newcommand{\TC}[1]{\class{TC^{#1}}} \newcommand{\ShP}{\class{\# P}} \newcommand{\PaP}{\class{\oplus P}} \newcommand{\PCP}{\class{PCP}} \newcommand{\kMIP}[1]{\class{#1\mbox{-}MIP}} \newcommand{\MIP}{\class{MIP}} $
$ \newcommand{\textprob}[1]{\text{#1}} \newcommand{\mathprob}[1]{\textbf{#1}} \newcommand{\Satisfiability}{\textprob{Satisfiability}} \newcommand{\SAT}{\textprob{SAT}} \newcommand{\TSAT}{\textprob{3SAT}} \newcommand{\USAT}{\textprob{USAT}} \newcommand{\UNSAT}{\textprob{UNSAT}} \newcommand{\QPSAT}{\textprob{QPSAT}} \newcommand{\TQBF}{\textprob{TQBF}} \newcommand{\LinProg}{\textprob{Linear Programming}} \newcommand{\LP}{\mathprob{LP}} \newcommand{\Factor}{\textprob{Factoring}} \newcommand{\CircVal}{\textprob{Circuit Value}} \newcommand{\CVAL}{\mathprob{CVAL}} \newcommand{\CircSat}{\textprob{Circuit Satisfiability}} \newcommand{\CSAT}{\textprob{CSAT}} \newcommand{\CycleCovers}{\textprob{Cycle Covers}} \newcommand{\MonCircVal}{\textprob{Monotone Circuit Value}} \newcommand{\Reachability}{\textprob{Reachability}} \newcommand{\Unreachability}{\textprob{Unreachability}} \newcommand{\RCH}{\mathprob{RCH}} \newcommand{\BddHalt}{\textprob{Bounded Halting}} \newcommand{\BH}{\mathprob{BH}} \newcommand{\DiscreteLog}{\textprob{Discrete Log}} \newcommand{\REE}{\mathprob{REE}} \newcommand{\QBF}{\mathprob{QBF}} \newcommand{\MCSP}{\mathprob{MCSP}} \newcommand{\GGEO}{\mathprob{GGEO}} \newcommand{\CKTMIN}{\mathprob{CKT-MIN}} \newcommand{\MINCKT}{\mathprob{MIN-CKT}} \newcommand{\IdentityTest}{\textprob{Identity Testing}} \newcommand{\Majority}{\textprob{Majority}} \newcommand{\CountIndSets}{\textprob{\#Independent Sets}} \newcommand{\Parity}{\textprob{Parity}} \newcommand{\Clique}{\textprob{Clique}} \newcommand{\CountCycles}{\textprob{#Cycles}} \newcommand{\CountPerfMatchings}{\textprob{\#Perfect Matchings}} \newcommand{\CountMatchings}{\textprob{\#Matchings}} \newcommand{\CountMatch}{\mathprob{\#Matchings}} \newcommand{\ECSAT}{\mathprob{E#SAT}} \newcommand{\ShSAT}{\mathprob{#SAT}} \newcommand{\ShTSAT}{\mathprob{#3SAT}} \newcommand{\HamCycle}{\textprob{Hamiltonian Cycle}} \newcommand{\Permanent}{\textprob{Permanent}} \newcommand{\ModPermanent}{\textprob{Modular Permanent}} \newcommand{\GraphNoniso}{\textprob{Graph Nonisomorphism}} \newcommand{\GI}{\mathprob{GI}} \newcommand{\GNI}{\mathprob{GNI}} \newcommand{\GraphIso}{\textprob{Graph Isomorphism}} \newcommand{\QuantBoolForm}{\textprob{Quantified Boolean Formulae}} \newcommand{\GenGeography}{\textprob{Generalized Geography}} \newcommand{\MAXTSAT}{\mathprob{Max3SAT}} \newcommand{\GapMaxTSAT}{\mathprob{GapMax3SAT}} \newcommand{\ELIN}{\mathprob{E3LIN2}} \newcommand{\CSP}{\mathprob{CSP}} \newcommand{\Lin}{\mathprob{Lin}} \newcommand{\ONE}{\mathbf{ONE}} \newcommand{\ZERO}{\mathbf{ZERO}} \newcommand{\yes} \newcommand{\no} $

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{\ket}[1]{| #1 \rangle} \newcommand{\bra}[1]{\langle #1 |} \newcommand{\braket}[2]{\langle #1 | #2 \rangle} \newcommand{\ketbra}[1]{| #1 \rangle\langle #1 |} \newcommand{\e}{\varepsilon} \newcommand{\eps}{\varepsilon} \newcommand{\from}{\colon} \newcommand{\super}[2]{#1^{(#2)}} \newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}} \newcommand{\tensor}{\otimes} \newcommand{\eset}{\emptyset} \newcommand{\sse}{\subseteq} \newcommand{\sst}{\substack} \newcommand{\ot}{\otimes} \newcommand{\Esst}[1]{\bbE_{\substack{#1}}} \newcommand{\vbig}{\vphantom{\bigoplus}} \newcommand{\seteq}{\mathrel{\mathop:}=} \newcommand{\defeq}{\stackrel{\mathrm{def}}=} \newcommand{\Mid}{\mathrel{}\middle|\mathrel{}} \newcommand{\Ind}{\mathbf 1} \newcommand{\bits}{\{0,1\}} \newcommand{\sbits}{\{\pm 1\}} \newcommand{\R}{\mathbb R} \newcommand{\Rnn}{\R_{\ge 0}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\C}{\mathbb C} \newcommand{\A}{\mathbb A} \newcommand{\Real}{\mathbb R} \newcommand{\mper}{\,.} \newcommand{\mcom}{\,,} \DeclareMathOperator{\Id}{Id} \DeclareMathOperator{\cone}{cone} \DeclareMathOperator{\vol}{vol} \DeclareMathOperator{\val}{val} \DeclareMathOperator{\opt}{opt} \DeclareMathOperator{\Opt}{Opt} \DeclareMathOperator{\Val}{Val} \DeclareMathOperator{\LP}{LP} \DeclareMathOperator{\SDP}{SDP} \DeclareMathOperator{\Tr}{Tr} \DeclareMathOperator{\Inf}{Inf} \DeclareMathOperator{\size}{size} \DeclareMathOperator{\poly}{poly} \DeclareMathOperator{\polylog}{polylog} \DeclareMathOperator{\min}{min} \DeclareMathOperator{\max}{max} \DeclareMathOperator{\argmax}{arg\,max} \DeclareMathOperator{\argmin}{arg\,min} \DeclareMathOperator{\qpoly}{qpoly} \DeclareMathOperator{\qqpoly}{qqpoly} \DeclareMathOperator{\conv}{conv} \DeclareMathOperator{\Conv}{Conv} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\sign}{sign} \DeclareMathOperator{\perm}{perm} \DeclareMathOperator{\mspan}{span} \DeclareMathOperator{\mrank}{rank} \DeclareMathOperator{\E}{\mathbb E} \DeclareMathOperator{\pE}{\tilde{\mathbb E}} \DeclareMathOperator{\Pr}{\mathbb P} \DeclareMathOperator{\Span}{Span} \DeclareMathOperator{\Cone}{Cone} \DeclareMathOperator{\junta}{junta} \DeclareMathOperator{\NSS}{NSS} \DeclareMathOperator{\SA}{SA} \DeclareMathOperator{\SOS}{SOS} \DeclareMathOperator{\Stab}{\mathbf Stab} \DeclareMathOperator{\Det}{\textbf{Det}} \DeclareMathOperator{\Perm}{\textbf{Perm}} \DeclareMathOperator{\Sym}{\textbf{Sym}} \DeclareMathOperator{\Pow}{\textbf{Pow}} \DeclareMathOperator{\Gal}{\textbf{Gal}} \DeclareMathOperator{\Aut}{\textbf{Aut}} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\cE}{\mathcal{E}} \newcommand{\E}{\mathbb{E}} \newcommand{\pE}{\tilde{\mathbb{E}}} \newcommand{\N}{\mathbb{N}} \renewcommand{\P}{\mathcal{P}} \notag $
$ \newcommand{\sleq}{\ensuremath{\preceq}} \newcommand{\sgeq}{\ensuremath{\succeq}} \newcommand{\diag}{\ensuremath{\mathrm{diag}}} \newcommand{\support}{\ensuremath{\mathrm{support}}} \newcommand{\zo}{\ensuremath{\{0,1\}}} \newcommand{\pmo}{\ensuremath{\{\pm 1\}}} \newcommand{\uppersos}{\ensuremath{\overline{\mathrm{sos}}}} \newcommand{\lambdamax}{\ensuremath{\lambda_{\mathrm{max}}}} \newcommand{\rank}{\ensuremath{\mathrm{rank}}} \newcommand{\Mslow}{\ensuremath{M_{\mathrm{slow}}}} \newcommand{\Mfast}{\ensuremath{M_{\mathrm{fast}}}} \newcommand{\Mdiag}{\ensuremath{M_{\mathrm{diag}}}} \newcommand{\Mcross}{\ensuremath{M_{\mathrm{cross}}}} \newcommand{\eqdef}{\ensuremath{ =^{def}}} \newcommand{\threshold}{\ensuremath{\mathrm{threshold}}} \newcommand{\vbls}{\ensuremath{\mathrm{vbls}}} \newcommand{\cons}{\ensuremath{\mathrm{cons}}} \newcommand{\edges}{\ensuremath{\mathrm{edges}}} \newcommand{\cl}{\ensuremath{\mathrm{cl}}} \newcommand{\xor}{\ensuremath{\oplus}} \newcommand{\1}{\ensuremath{\mathrm{1}}} \notag $
$ \newcommand{\transpose}[1]{\ensuremath{#1{}^{\mkern-2mu\intercal}}} \newcommand{\dyad}[1]{\ensuremath{#1#1{}^{\mkern-2mu\intercal}}} \newcommand{\nchoose}[1]{\ensuremath} \newcommand{\generated}[1]{\ensuremath{\langle #1 \rangle}} \notag $
$ \newcommand{\eqdef}{\mathbin{\stackrel{\rm def}{=}}} \newcommand{\R} % real numbers \newcommand{\N}} % natural numbers \newcommand{\Z} % integers \newcommand{\F} % a field \newcommand{\Q} % the rationals \newcommand{\C}{\mathbb{C}} % the complexes \newcommand{\poly}} \newcommand{\polylog}} \newcommand{\loglog}}} \newcommand{\zo}{\{0,1\}} \newcommand{\suchthat} \newcommand{\pr}[1]{\Pr\left[#1\right]} \newcommand{\deffont}{\em} \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}} \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance \newcommand{\xor}{\oplus} \newcommand{\GF}{\mathrm{GF}} \newcommand{\eps}{\varepsilon} \notag $
$ \newcommand{\class}[1]{\mathbf{#1}} \newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements \newcommand{\BPP}{\class{BPP}} \newcommand{\NP}{\class{NP}} \newcommand{\RP}{\class{RP}} \newcommand{\coRP}{\coclass{RP}} \newcommand{\ZPP}{\class{ZPP}} \newcommand{\BQP}{\class{BQP}} \newcommand{\FP}{\class{FP}} \newcommand{\QP}{\class{QuasiP}} \newcommand{\VF}{\class{VF}} \newcommand{\VBP}{\class{VBP}} \newcommand{\VP}{\class{VP}} \newcommand{\VNP}{\class{VNP}} \newcommand{\RNC}{\class{RNC}} \newcommand{\RL}{\class{RL}} \newcommand{\BPL}{\class{BPL}} \newcommand{\coRL}{\coclass{RL}} \newcommand{\IP}{\class{IP}} \newcommand{\AM}{\class{AM}} \newcommand{\MA}{\class{MA}} \newcommand{\QMA}{\class{QMA}} \newcommand{\SBP}{\class{SBP}} \newcommand{\coAM}{\class{coAM}} \newcommand{\coMA}{\class{coMA}} \renewcommand{\P}{\class{P}} \newcommand\prBPP{\class{prBPP}} \newcommand\prRP{\class{prRP}} \newcommand\prP{\class{prP}} \newcommand{\Ppoly}{\class{P/poly}} \newcommand{\NPpoly}{\class{NP/poly}} \newcommand{\coNPpoly}{\class{coNP/poly}} \newcommand{\DTIME}{\class{DTIME}} \newcommand{\TIME}{\class{TIME}} \newcommand{\SIZE}{\class{SIZE}} \newcommand{\SPACE}{\class{SPACE}} \newcommand{\ETIME}{\class{E}} \newcommand{\BPTIME}{\class{BPTIME}} \newcommand{\RPTIME}{\class{RPTIME}} \newcommand{\ZPTIME}{\class{ZPTIME}} \newcommand{\EXP}{\class{EXP}} \newcommand{\ZPEXP}{\class{ZPEXP}} \newcommand{\RPEXP}{\class{RPEXP}} \newcommand{\BPEXP}{\class{BPEXP}} \newcommand{\SUBEXP}{\class{SUBEXP}} \newcommand{\NTIME}{\class{NTIME}} \newcommand{\NL}{\class{NL}} \renewcommand{\L}{\class{L}} \newcommand{\NQP}{\class{NQP}} \newcommand{\NEXP}{\class{NEXP}} \newcommand{\coNEXP}{\coclass{NEXP}} \newcommand{\NPSPACE}{\class{NPSPACE}} \newcommand{\PSPACE}{\class{PSPACE}} \newcommand{\NSPACE}{\class{NSPACE}} \newcommand{\coNSPACE}{\coclass{NSPACE}} \newcommand{\coL}{\coclass{L}} \newcommand{\coP}{\coclass{P}} \newcommand{\coNP}{\coclass{NP}} \newcommand{\coNL}{\coclass{NL}} \newcommand{\coNPSPACE}{\coclass{NPSPACE}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\LINSPACE}{\class{LINSPACE}} \newcommand{\qP}{\class{\tilde{P}}} \newcommand{\PH}{\class{PH}} \newcommand{\EXPSPACE}{\class{EXPSPACE}} \newcommand{\SigmaTIME}[1]{\class{\Sigma_{#1}TIME}} \newcommand{\PiTIME}[1]{\class{\Pi_{#1}TIME}} \newcommand{\SigmaP}[1]{\class{\Sigma_{#1}P}} \newcommand{\PiP}[1]{\class{\Pi_{#1}P}} \newcommand{\DeltaP}[1]{\class{\Delta_{#1}P}} \newcommand{\ATIME}{\class{ATIME}} \newcommand{\ASPACE}{\class{ASPACE}} \newcommand{\AP}{\class{AP}} \newcommand{\AL}{\class{AL}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\VNC}[1]{\class{VNC^{#1}}} \newcommand{\NC}[1]{\class{NC^{#1}}} \newcommand{\AC}[1]{\class{AC^{#1}}} \newcommand{\ACC}[1]{\class{ACC^{#1}}} \newcommand{\TC}[1]{\class{TC^{#1}}} \newcommand{\ShP}{\class{\# P}} \newcommand{\PaP}{\class{\oplus P}} \newcommand{\PCP}{\class{PCP}} \newcommand{\kMIP}[1]{\class{#1\mbox{-}MIP}} \newcommand{\MIP}{\class{MIP}} $
$ \newcommand{\textprob}[1]{\text{#1}} \newcommand{\mathprob}[1]{\textbf{#1}} \newcommand{\Satisfiability}{\textprob{Satisfiability}} \newcommand{\SAT}{\textprob{SAT}} \newcommand{\TSAT}{\textprob{3SAT}} \newcommand{\USAT}{\textprob{USAT}} \newcommand{\UNSAT}{\textprob{UNSAT}} \newcommand{\QPSAT}{\textprob{QPSAT}} \newcommand{\TQBF}{\textprob{TQBF}} \newcommand{\LinProg}{\textprob{Linear Programming}} \newcommand{\LP}{\mathprob{LP}} \newcommand{\Factor}{\textprob{Factoring}} \newcommand{\CircVal}{\textprob{Circuit Value}} \newcommand{\CVAL}{\mathprob{CVAL}} \newcommand{\CircSat}{\textprob{Circuit Satisfiability}} \newcommand{\CSAT}{\textprob{CSAT}} \newcommand{\CycleCovers}{\textprob{Cycle Covers}} \newcommand{\MonCircVal}{\textprob{Monotone Circuit Value}} \newcommand{\Reachability}{\textprob{Reachability}} \newcommand{\Unreachability}{\textprob{Unreachability}} \newcommand{\RCH}{\mathprob{RCH}} \newcommand{\BddHalt}{\textprob{Bounded Halting}} \newcommand{\BH}{\mathprob{BH}} \newcommand{\DiscreteLog}{\textprob{Discrete Log}} \newcommand{\REE}{\mathprob{REE}} \newcommand{\QBF}{\mathprob{QBF}} \newcommand{\MCSP}{\mathprob{MCSP}} \newcommand{\GGEO}{\mathprob{GGEO}} \newcommand{\CKTMIN}{\mathprob{CKT-MIN}} \newcommand{\MINCKT}{\mathprob{MIN-CKT}} \newcommand{\IdentityTest}{\textprob{Identity Testing}} \newcommand{\Majority}{\textprob{Majority}} \newcommand{\CountIndSets}{\textprob{\#Independent Sets}} \newcommand{\Parity}{\textprob{Parity}} \newcommand{\Clique}{\textprob{Clique}} \newcommand{\CountCycles}{\textprob{#Cycles}} \newcommand{\CountPerfMatchings}{\textprob{\#Perfect Matchings}} \newcommand{\CountMatchings}{\textprob{\#Matchings}} \newcommand{\CountMatch}{\mathprob{\#Matchings}} \newcommand{\ECSAT}{\mathprob{E#SAT}} \newcommand{\ShSAT}{\mathprob{#SAT}} \newcommand{\ShTSAT}{\mathprob{#3SAT}} \newcommand{\HamCycle}{\textprob{Hamiltonian Cycle}} \newcommand{\Permanent}{\textprob{Permanent}} \newcommand{\ModPermanent}{\textprob{Modular Permanent}} \newcommand{\GraphNoniso}{\textprob{Graph Nonisomorphism}} \newcommand{\GI}{\mathprob{GI}} \newcommand{\GNI}{\mathprob{GNI}} \newcommand{\GraphIso}{\textprob{Graph Isomorphism}} \newcommand{\QuantBoolForm}{\textprob{Quantified Boolean Formulae}} \newcommand{\GenGeography}{\textprob{Generalized Geography}} \newcommand{\MAXTSAT}{\mathprob{Max3SAT}} \newcommand{\GapMaxTSAT}{\mathprob{GapMax3SAT}} \newcommand{\ELIN}{\mathprob{E3LIN2}} \newcommand{\CSP}{\mathprob{CSP}} \newcommand{\Lin}{\mathprob{Lin}} \newcommand{\ONE}{\mathbf{ONE}} \newcommand{\ZERO}{\mathbf{ZERO}} \newcommand{\yes} \newcommand{\no} $

Click here to go back to the original version.

What does Popular Science Mean to Me?

(See here for the original Mandarin version)

In the past month, I’ve been mainly working on preparing this two-week-long mini-course on computation. Unexpectedly, an incident in the last few days of the mini-course made me seriously rethink about what’s the essence of popular science. Do we really need popular science? Could popular science harm scientific progress?

But anyway, let’s start by clarifying the definition of popular science! If we think a few steps further, we will notice that there are lots of different forms and levels of popular science!

Public Media: from news, radios, podcasts, videos to magazines, these are probably the most common source of popular science for the general public. Thousands of media workers try hard to translate frontier scientific research into a language that ordinary people can comprehend every day. However, the quality of popular science in this category could vary significantly. Many people live with exaggerated headlines in the jungle of market competition, while some hold on to professional persistence and win many diehard fans.

Popular Science Books: if one has more time and effort, popular science books are probably the next common source of popular science. Similarly, there’s a wide variety and diverse level of books in the science section in a bookstore. Either being written by outstanding scientists or forwarded by famous public figures, popular science books are usually more focused on a specific discipline ranging from physics, chemistry, mathematics, biology, psychology, and beyond. Unlike public media, popular science books are usually more systematic and sometimes even have multiple books published as a set. Nevertheless, since popular science books are not textbooks and are facing the general public, their contents still tend to focus on high-level stories and assume less educational background from the readers, sometimes even omitting some details.

Online Courses: I sometimes envy the kids nowadays who can easily access online lessons from top universities. Even though some online courses might be simplified, through homework, interactions on online forums, or even simple experiments, it’s easy to achieve learning effects that cannot be done merely by reading popular science books.

General Education Courses in Universities: These are perhaps the highest popular science level. In a university’s GenEd course, the professor will have an entire semester to teach, and the students also have much more educational background than the general public. Even though the major of the students might not match the topic of the course, the professor could still cover broader and deeper content since college students usually have a basic level of logical thinking and communication skill. For example, last semester, I was a teaching assistant for the GenEd course “Science and Cooking” at Harvard (there’s also an online version, but it is much simplified). In about three months, the professors explained many fundamental physics and chemistry concepts that are usually only taught in (elementary) professional courses to students from all departments.

What about the position of my mini-course? I locate it at the level between an online course and a university’s GenEd course. Indeed, I sacrificed the depth of the mini-course due to the broad nature of the course’s content. Meanwhile, I also expect myself to put enough insights and core concepts so that the students can have more foundation for their future explorations. As a next step, I also plan to start drafting a popular science book about the same topic of this mini-course. Hopefully, I can use these different formats to present my understanding and thoughts on the cross-disciplinary knowledge about computation.

I believe everyone must have slightly different opinions on the purpose of popular science. Some might think the goal is to turn abstruse scientific knowledge into something comprehensible for the general public. Some might think this is an excellent way to gain popularity. Some might simply enjoy the process of teaching and writing.

But in my case, my original motivation for doing popular science is two-fold: first, let people around me know better about what I’m doing. For example, I wrote a book (in Mandarin) about computational complexity before I graduated from college and sent physical copies to friends and families. Even though my mom and dad didn’t seem to finish the book, a friend of mine spent six months reading the book without any prior background, and now she has a rough sense of binary numbers and Turing machines! Second, writing popular science articles also serves as a process of meditation and elevation for me. Throughout the writing period, I have to keep challenging my understanding from the bottom to the top and guessing what could be the potential confusion for readers. It’s often the case that I could come up with an unexpected narrative and understanding after multiple rounds of back and forth thinking and writing.

However, looking at my mini-course, the time and efforts seem to be disproportional to the motivations described above. Indeed, another big incentive is the joy of interacting with the audience, readers, students from teaching and writing. At least to me, such pleasure is always irreplaceable from any other experience.

Ok, are these all popular science mean to me? Standing from a more objective perspective, I have a few words to say.

The knowledge distribution is still highly uneven under the current education system. From my own experience, I vividly remember how shocked I was after I knew the high school education of my cohorts at National Taiwan University (sadly, I’m the one with fewer educational resources). If one doesn’t have good books and materials for learning, then no matter how smart they are, it’s just impossible for them to create the knowledge from thousands of years of human wisdom from scratch. After coming to Harvard, I was further astonished by the importance of big pictures and how that can make a huge difference. Having good basic concepts and understanding the big directions and appreciation in a field as early as possible can drastically improve learning efficiency. However, suitable materials and big pictures are still not that approachable to ordinary people even though we are now in an era of the Internet.

Everything should be made as simple as possible, but not simpler.

- Albert Einstein.

On the other hand, there’s another special role of popular science in modern society: enhancing the interaction and learning across different disciplines. And this is precisely the core value of my mini-course. As each (scientific) field has been flourishing in the past few decades, frontier knowledge also becomes more involved and abstruse. In the meantime, the purpose of cross-disciplinary interaction and learning is a bit different from receiving a solid undergraduate or even graduate training in a field. The focus would be on exchanging core concepts and tools to inspire each other with new ideas in their original field (of course, there are different types of interdisciplinary interactions).

Next, let’s move on to the central topic of this article: could popular science be dangerous?

From my observation, there are three main arguments against popular science: (i) popular science would create an illusion of knowing a lot, (ii) popular science makes people lazy, and the learning effect is not solid, (iii) the oversimplification in popular science might even turn the scientific progress backward.

I agree with the first two criticisms. Some “bad” popular science resources can easily cause such issues in society. But I also want to point out a blind spot of these arguments: those who will have the illusions mentioned earlier after reading/watching/studying popular science would easily have similar illusions anyway without popular science! On the contrary, if the quality of a popular science resource is high, it can let the audience realize more about their ignorance and build up the motivation to pursue further studies (if they are not entirely laypeople). This attitude is also what I want to emphasize in my mini-course!

Our knowledge can only be finite, while our ignorance must necessarily be infinite.

- Karl Popper.

So to me, (i) and (ii) are more like a reminder for popular science workers rather than an actual danger.

As for (iii), this might be a bit subtle, and as a junior member in academia, I would like to provide a few of my thoughts and hopefully stimulate more discussion on this line of debate!

Does science keep progressing? If research cannot push the “progress” in science, could it still be an excellent scientific study? In the ivory tower of academia, one might have been learning the so-called “correct” scientific knowledge and hence treating those died-out theories as useless. However, this is not the truth. If we look back at the history of science, most of the existing knowledge is heavily inspired by the “wrong theories” from the past. Moreover, in the scientific frontier, many prestigious theories nowadays were also born from incorrect understandings and hypotheses.

So, I think it’s hazardous to simplify the development of science into a single narrative. This might be even more harmful to scientific progress than a bad popular science! From the angle of evolution, following a single voice might explain the world well but also has a smaller driving force to move forward. On the contrary, when there are many variations, even though many of them will be eliminated or move backward, the variations give us hope to move toward the next “paradigm shift”!

Self Reflection and Expectation

I hope I have convinced the reader that a “good popular science” can give more construction than destruction to society, scientific development, and cross-disciplinary interactions. But of course, this depends on what I mean by a “good popular science,” and is it realizable in reality? How do we determine the quality of work in popular science?

In my opinion, a necessary condition of being a good popular science is letting the readers/students know what is skipped and simplified and what is unknown to us. In the end, a teacher or a book cannot control how the recipient interprets and understands the knowledge. So outside presenting the materials, it is of great importance to provide reminders and warnings. Let alone popular science, even in scientific research or learning, being humble and knowing what one is ignorant of is extremely crucial. The following is a slide from my mini-course’s last lecture, and I hope we can constantly reflect on ourselves.

So is good popular science realizable in reality? This is like asking a scientist whether it’s possible to have a perfect theory. Namely, it depends on personal belief. At least I’m optimistic since I did see some good books or online lectures. But as for how to determine the quality of popular science, it probably relies on one’s eyes and tastes. Like any book or course must have positive and negative comments, and the majority vote might not always reveal the truth, one still has to build up critical and independent thinking.

Finally, I’d like to leave a few sentences for my future self regarding the unexpected incident during the mini-course. When being criticized or attacked, I don’t need to have an immediate reaction and even forget to reexamine myself. Everyone makes mistakes, and the most important thing is to accept them and improve oneself from them. Wish me in the future can be confident but also be humble, be curious but also be rigorous.

This is Biology (English Version)

(See here for the original Mandarin version)

This September in Boston didn’t prolong the blazing heat in the summer, but was full of the feeling of autumn. The wind kissed my face while I rode the bike down the bridge across Charles river, and made me feel like swimming in the cold water. The unusual cold September caused me to expect the early arrival of fall color, however, the theory hike on the first weekend of October was not as colorful as imagine. Unsurprisingly, the theory and reality have a gap again!

I immediately started an exciting conversation about cross-disciplinary research between CS and Neuroscience with a new-coming postdoc right after we started the hike on the White Dot trail of Mt. Monadnock. We talked a little bit about what problems we’ve been exploring respectively, and then moved on the difference between biology, CS, and Physics research. What kind of biology research is “closer to the reality”? How to justify a mathematical model being “biologically-plausible”? Amongst our intense debate, I suddenly saw the deep gulf (which is quite obvious but I didn’t realize it before) between biologists and computer scientists: when talking about biological plausibility, the two party are basically talking about totally different things!

As a CS-trained student, I understand that when we talk about biological plausibility, what we have in mind are “conditions” or “biological constraints” such as the local connectivity or the sparse activities of neurons. Then, the next step we usually do is using mathematical models to capture these conditions and start either abstract deductive analysis or computer simulation. However, for biologists, biological plausibility does not necessarily refer to a concrete checklist. It’s more like after a huge amount of readings, experiments, and discussions, each of them gradually build up their own intuition and worldview. As the experiments in biology contain so much noises and special cases, it’s nearly impossible to write down rigorous mathematical constraints and check them one by one objectively. So sometimes it’s actually quite interesting to see that biologists might not be that biologically plausible as computer scientists would imagine!

Cross-disciplinary research is challenging, not only one has to learn lots of knowledge from the other fields, in my opinion the most difficult part is to understand and appreciate the beauty in the other fields. I occasionally saw on Facebook a book recommendation on This is Biology by Ernst Mayr. Through this book, I finally got a chance to peak into the big picture of a great (evolutionary) biologist on Biology.

A roller coaster ride of philosophy of biology

Originally I just thought to ask my roommate, who is an evolutionary biologist, to read and discuss This is Biology together. In the end, he enthusiastically invited friends from several different fields to form a reading group and this began a roller coaster ride of building up my philosophy of biology.

The reason why I call this a roller coaster ride is that I had been challenged and reshaped multiple times during these three months. Now that the ride has ended, I’m ready to bring my newly built value and belief to start my next journey. As there must be much more stimulus and growth in my future exploration in cross-disciplinary research, here I’m going to briefly take some notes on the enlightenments and changes This is Biology had brought to me.

The beauty and challenge in Biology

A physics friend used to joke with me that Biology is like collecting stamps. And its beauty is about the diversity and complexity in the Nature while the job of biologists is collecting and recording new discoveries. Relatively speaking, Physics and Math seem to dig deeper into the hidden symmetry and structure in the Nature and the abstract world. Implicitly this is kind of showing some superiority from Physics over Biology. Indeed, physicists often have the confidence of having deeper understanding of the world. In contrast, as Biology is a relatively young field, many sub-fields are still in the stage of collecting more and more data and observations from experiments. But such a difference in their current development does not imply which field is easier and which is more difficult. In the frontier of a scientific field, as long as one keeps the curiosity to the unknown, the rigor of knowledge, and the persistence in quality, every one step further is incomparably important and irreplaceable.

I grew up in an environment with very less exposure to the Nature. Amongst the hustle and bustle in the city and the fantasy of abstract (mathematical) world, I had always had a hard time to understand and appreciate the beauty in Biology. I still remember vividly the first time when I talked about research with my roommate. When he told me he’s going to spend a couple of years to take photos of butterflies’ specimens and write programs to analyze the shape and color of their wings, I really don’t understand why this counted as “doing research”. Why he is going to spend so much time on a single species out of millions? Why six specimens for each type of butterfly is sufficient? Why they can make any claim and result under seemingly weak correlations and evidences?

Indeed, from the perspectives of Physics and Math, Biology may not be listed in the Hall of Fame for intellectual pursuit. But why do we compare Biology with Physics and Math? Directly comparing these different disciplines is like comparing music and painting. Individuals’ preference could influence rational thinking and discussion. In the end, the difference of “the sense of beauty” among different fields causes huge misunderstandings and even discriminations. So why not let us throw away our prejudice, and try to revisit the beauty of Biology.

From collecting stamps to playing jigsaw puzzle

Biodiversity is undoubtedly the main reason why people would think of biology as like collecting stamps. While currently there are hundreds of sub-atomic atoms known in the world, just the number of butterfly species on earth is nearly 20 thousands. If we think even more careful about how to classify organisms, then we will notice that even properly defining what does a species mean is a highly non-trivial task. As biodiversity is so messy and dirty, then where’s its beautiful part? In some senses, biology indeed looks like collecting stamps since many works are spent on collecting, classifying, and processing data. So is this data collection process the beauty of biodiversity? To me, such a “collecting stamps” stage is just the first step of appreciating biodiversity. The real exciting part of biologists’ job is to figure out the underlying pattern and difference among the huge amount of noisy data.

Thus, in my opinion, the beauty of biology is more on the stage after collecting stamps. And I call it the “playing jigsaw puzzle” stage. At this stage, people need to put the messy data points (i.e., pieces of a jigsaw puzzle) with certain correlations together. Moreover, one should not be interfered by the superficial similarity (e.g., in the jigsaw puzzle below, different orange pieces might come from different orange cats!). Even worse, most of the time it is impossible to collect enough pieces and hence biologists often have to figure out something insightful without seeing the whole picture.

As a comparison, physics and mathematics are more like playing boardgames or strategy games where one of the main challenges is to walk through a huge maze with small number of local choices/rules and huge global possibilities.

So in order to build up a sense of beauty for appreciating biology, I think we should temporarily loosen our insistence of logical perfection (in the sense of having a theory from first principles) and focus more on how to get something useful and interesting out from the huge and messy experimental data. If one don’t appreciate such kinds of the beauty, then it might also be hard to have a deeper appreciation in some of the modern developments/research in biology. But of course, I’m not here to ask every reader to change themselves and start to like biology after reading this article. I guess the point is more about discussing the intrinsic differences between biology and physics (also math and other natural sciences). In the end, I really hope people from different fields can have less misunderstandings and discriminations on each other. And if having more time, even know a little about the challenges and hopes in other fields.

Anyway, as I started to appreciate more on the beauty of playing jigsaw puzzle in biology, I realized much more exciting and cute aspects to explore. Here I would like to share three recent relevations I got: the beauty of diversity, the beauty of individual, and the beauty of experiment.

The beauty of diversity: I vividly recall that when I first met my roommate, I truly didn’t understand why he is so excited when seeing a new ant species (to be honest, I still haven’t fully got it…). In retrospect, my previous pursuit of beauty was more about abstractions, forms, and symmetries while the beauty of biodiversity is almost on the other side of a coin. Particularly, it’s often about concrete objects, real practices, and special cases. Nevertheless, although the two senses of beauty are very different, they are not necessarily conflicting with each other. Each person would have different inclination toward these two types of beauty due to their family and education. And it is totally fine for a person to stick to the beauty that they find more comfortable with. But after opening up the eyes for the other type of beauty, the whole world will start to look more colorful. In my case, after having more and more appreciations on the beauty of biodiversity, every flower and tree on the street began to tell their stories to me. I also got a wider range of feelings on the surroundings and knowledges and sometimes they could even bring me inspirations and joys.

The beauty of individual: Every organism is a unique existence in the world, unlike every hydrogen atom basically looks exactly the same in the experiment. While biologists are working on finding patterns within biodiversity, the discovery of patterns could also bring new understandings on an individual through their differences. Through building up theories in biology, we not only aim for figuring out the governing rules behind the reality, but also try to find our own new perspectives and angles to comprehend the subtle beauty of individual.

The beauty of experiment: In physics, people verify theoretical models through extremely precise experiments. In contrast, experiments in biology often cannot achieve such precision and hence people often have to make claims from limited data and resources. For example, in the butterfly research of my roommate, he uses only six individuals for each species (and he told me this is the highest standard). This is not because they don’t want or they cannot use a hundred individuals for each species. It is simply infeasible for them to conduct such a huge experiment under limited time and hands. Such reality constraints (e.g., number of data points, noise in the data, etc.) are like the logical rules in mathematics. Biologists really need to struggle among these constraints and design meaningful experiments. I would say this might be not much easier than mathematician walking through the labyrinth of axioms.


Here let me give two examples about decision making in neuroscience to let the readers appreciate the beauty behind experiments design.

Some background information first. In the study of decision making, a (short-term) goal of neuroscientists is to identify certain network structures that can be mapped to a decision making mechanism. Hence, one big challenge is to rule out as much alternatives as possible so that the experimental findings can (only) be explained by the proposed theoretical model. So in an experiment, other than designing devices, one also needs to design animal behavior tasks as well as the interpretations of various possible outcomes.

The first experiment is about the decision making related to somatosensory system. In the experiment, the fingers of a monkey will be stimulated by a 20Hz stimulus for 500ms. After a while, another stimulus with a different frequency will be sent out and the monkey has to decide if the frequency of the second stimulus is higher or lower than that of the first stimulus.

The second experiment is about the decision making related to visual system. In the experiment, a monkey first fixate on the central fixation spot of a screen (usually a cross) while there are dots presented and moving around either from left to right or the other way back. Then the monkey has to decide if the dots are moving toward left or toward right. Furthermore, there is a fraction of dots moving randomly to adjust the difficulty of the decision making task.

The above two experiments are both very classic in the literature of decision making. But is one of them better than the other? If you think carefully, you will notice a big issue in the first experiment: there is a time gap between the two stimuli and hence the monkey has to "memorize" the first vibration and compare with the second one afterward. Note that this additional requirement of memorization (implicitly) increases the complexity of the task and hence makes it harder for the experimentalists to dissect the specific network that is responsible for the decision task only. As for the second experiment, it first bypasses the memory issue by presenting all the information simultaneously. Second, it provides an adjustable parameter on the fraction of randomly moving dots to enable a more quantitative study of the underlying mechanism. Finally, the initial fixation is like a "reboot" which makes sure the monkey starts from similar initial condition in every trial.

Different challenges: the lack of symmetry, emergence properties, objective meanings

To further establish a sense of beauty of biology, one has to embrace and understand the its challenges. Here I’d like to emphasize the following three challenges of biology from my personal view: the lack of symmetry, emergence properties, the existence of objective meanings.

The lack of symmetry: It’s not an exaggeration to said that the great success of modern physics is established on top of the brilliant observations of symmetry and asymmetry of the physical world. Symmetries not only lead to rich mathematics but also restrict the search space and enable abstract analysis (recommended reading:The Unreasonable Effectiveness of Mathematics in Physics). However, the jungle of biology is seriously lack of those diverse and beautiful (and analyzable) symmetries. In my opinion, this is the root of the challenges to building good theories in biology. Thus, most of the mathematical or computational models in biology are more or less like a “description” as opposed to a “model” for the underlying reality.

Emergence properties: The so called emergence property in biology is conceptually very similar to the chaotic phenomenon in physics: a bunch of applications of simple rules induce complicated results. Personally, I like to use a theoretical CS concept to think about emergence properties: one-wayness, i.e., easy to compute/manipulate in the forward direction, but hard to revert back to the initial starting point. How does an embryo develop into a mature organism? How are genes mapped to phenotypes? How do neurons’ activities form computation, intelligence, and consciousness? Emergence properties make mechanical modeling and understanding become extremely challenging. Either we get a rough statistical understanding via macroscopic analysis, or getting some models that soon become too complicated to understand as well (e.g., using deep learning to build a model). Meanwhile, the reduction method that is commonly used in physics also often oversimplifies the emergence properties and cannot capture multiple aspects simultaneously. Perhaps we really need a new methodology/framework to the tradition physical and mathematical methods?

Objective meanings: People always like to endow meanings to whatever we see. I still vividly remember during my last trip to Antelope Canyon), besides being amazed by the extraordinary workmanship of the mother nature, I was also impressed by the creativity of the local tour guide. Within a few steps, you would hear something like “Look! This is the shark from Finding Nemo!” (see the figure below). I believe no one will believe that the mother nature purposefully sculpt a shark in the Antelope Canyon, however, this also reminds us to be aware of our own inductive bias while trying to understand the nature. This reminds me of the comparison of proximate cause and ultimate cause mentioned in the book. It is truly subtle to be clear on what type of explanation one is talking about, especially when it is about correlations and causations. In a non-axiomatized discipline like biology, people unavoidably have to learn how to move forward without induction and/or deduction. Most of the time, the main scientific method is then based on abductive reasoning. In other words, all the knowledges are built on top of observations instead of logical axioms. Thus, there’s even no the so called ground truth. There’s only a better explanation rather than the best explanation. Nonetheless, “a better explanation” itself is very subjective and the voice is often controlled by those experts in the field. Perhaps, it is impossible to achieve a fully objective consensus in biology?

What are the knowledge, understanding, and theory in biology?

All the above examples and perspectives are serving for a key message Mayr wanted to convey from the very beginning of the book: there’s a need of different/new set of methodology and philosophy of science for biology (because those have been dominated by physics). I still remember that I always disagree with this opinion of Mayr and thought that he didn’t know enough physics. But now, even though I still don’t know if Mayr really knew some physics or not, I do know that my previous understanding of biology was too shallow.

So here I’d like to record the transition of my mindset and hope to prevent the non-biologists reader from discriminating biology. Meanwhile, this can also be an opportunity for biologists (like my roommate) to have more senses on the common prejudice from students with physics and math background.

Philosophy of science: the misunderstandings between biologists and physicists

I had learned a little basic philosophy of science during my undergrad. It’s nothing more than logical positivism, Kuhn’s paradigm shift, and Popper’s falsification, etc. As ignorant as a kid, I had been regarding these as the axioms of doing science for a very long time. Not until I had much more independent thinking in the past few years did I realize the abundance of philosophy of science.

In the first paragraph of the philosophy of science section in the book, Mayr pointed out that even though there are several schools of thoughts, they still all center around physics (especially theoretical physics) and might not be that suitable for biology. I think this difference can be perfectly explained by the title of a famous paper of evolutionary biologist Stephen Jay Gould: Evolution as fact and theory. Notice that Gould didn’t say that evolution is reality or truth, while these two are exactly what most theoretical physicists are looking for! For example, this mindset can be seen from the title of the book by Nobel prize in physics laureate Roger Penrose:The Road to Reality).

Using more modern concepts to analyze the comparison of physics and biology, I would say the former is more like scientific realism while the latter is closer to instrumentalism. Simply speaking, scientific realism believes in the existence of “ideal theory” and advocates that the goal of scientific research is to move closer and closer to the ideal theory. However, instrumentalism also takes the opposite opinion and believes that scientific theories are tools for us to understand the world. Hence, the focus should be explaining and predicting real-world phenomena.

Of course, here I oversimplify the serious comparison and discussion on the different branches of philosophy of science. My main aim here is to plant some seeds in the readers’ mind so that you all can explore and build up your own philosophy of science (The Stanford Encyclopedia of Philosophy could be a good starting point). As a friendly reminder, it is important to keep in mind that philosophy of science ultimately is still just an assistant to help us clarifying the goal and essence of scientific research. It’s not the end and there’s no correct answer for it. Everyone can have different favors and the same person can even have different philosophical believes in different disciplines or sub-disciplines. If one can understand more perspectives, then this not only enrich your own thinking, but also help you to be able to think from other’s angle when talking to someone from a different field.

The role and possibility of math in biology?

As a theoretical computer scientist, an amateur mathematician, and a hobby physicist, I still have strong pursuit (and need) for math and the beauty of abstraction. However, all the challenges in biology we have discussed above hardly not make me wonder the possibility of applying math in biology. Recently I ran across this arXiv paper “A mathematician’s view of the unreasonable ineffectiveness of mathematics in biology” which gives a pretty good exposition on my concern. The author provides lots of observations and stories centering around the famous mathematician Israel Gelfand (who worked on biology after being well-established in pure math). I recommend it as a casual and enjoyable read.

My personal view is the following. Mathematics have been highly influenced by physics and many branches are kind of corresponding to a certain sub-discipline in physics. On the contrary, there’s very few examples of new mathematics that were inspired by biology. This is not saying that biology lacks of mathematical potential. Maybe it is the current mathematics are not ready for biology yet. We need someone to create new mathematics for biology!

But what kind of mathematics could be suitable for biology? Common mathematical tools used by bio-physicists or mathematical biologists are dynamical systems, differential equations, control theory, game theory, etc. In my opinion, there’s a lack of algorithmic lens. Here what I meant by algorithms is something more general than the Turing machine sense. I meant something to the level of software engineer where there are huge programs with multiple sub-programs and their sub-sub-programs. Using such an algorithmic/software engineering view to understand biological systems can not only provide an analytic/logical methodology but also give different levels and granularities of understandings. The current development of computational biology could be something that is closest to what I have in mind. But most of the works there are still in the stage of writing models and running simulations. There’s still no clean mathematical language that enables abstract analysis.

The reality of cross-disciplinary research, sympathy and understanding, next step

Besides the reading group for This is Biology, I also have been running a cross-disciplinary reading group (When neuroscience meets CS, math, and physics) with Brabeeba. These experiences make me fully understand the challenges of cross-disciplinary interactions are bi-directional: besides learning more from the other fields and thinking in their shoes, the conversation should also start from the basis of the other person being interested in learning what you can bring. I then realize that to do cross-disciplinary research in long-term, one should not only have solid foundations in different disciplines, but also build up the senses of beauty and/or even get recognized by these fields to some extent. Quantitatively speaking, one should arrive at the basic graduate student level in the other field!

After realizing the challenges in front of my cross-disciplinary agenda did make me a bit frustrated in the beginning. But now I feel super excited and am very looking forward to what I will get to in all the different directions I’m interested in. Hope that I won’t forget the importance of sympathizing and understanding the distinctions of different fields, and persistently push forward this lonely but fascinating journey.

(Thanks Brabeeba Wang and Wei-Ping Chan for many good suggestions for this post!)

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 (English Version)

(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!