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

Blog

A place to record my feeling, my thought, my exploration, and my growth. Since I intend to be casual here so I decided to use Madarin for most of the posts. I'll translate (with the help of google translate) some of the posts on request and put it here.

The Glass Bead Game

(See here for an English version)

說來慚愧,在今年以前,我從來沒有從頭到尾讀完一本英文書(可能英文論文也是…)。教科書通常要嘛是因為讀到一半學期就結束了,或只是拿來翻翻有需要的地方。小說或非小說類的書,總是因為讀的速度太慢加上理解程度不是那麼好,往往中途就放棄改買中文版了…疫情前要這樣搞還算容易,最多就是忍耐個半年一年就可以回台灣買中文書。不過疫情開始後,看不到下次回家是什麼時候了,而中文書的庫存也逐漸殆盡,於是我終於開始硬著頭皮緩慢地讀英文書了。

我本來就不是個看特別多書的人,一年可能也就看個十到二十本書,平時可能就睡前讀個半小時一小時。尤其我的自制能力可能還不錯,即使迷上了一本小說,我還是會很克制的一天就只讀個兩三個章節。所以就算是一本三百頁的中文小說好了,可能還是會要花個兩三個禮拜才讀完。不過這次迫於天災開始讀英文書,沒想到我開始認真看的第一本英文小說,從頭到尾四百多頁竟然花了我九個月才看完…換算成閱讀速度的話,我的中文閱讀速度幾乎是英文的15倍!

而這本我讀完的第一本英文小說,Hermann Hesse的《玻璃珠遊戲》(英譯:The Glass Bead Game;德文原名:Das Glasperlenspiel),其實原本是用德文寫的。如果我有生之年學了德文,可能又要再花個幾年才能把原文的版本讀完了…不過話說回來,在分享我的感想之前,還是得說讀英文小說(可惜這次我讀的小說原文是德文不是英文…)的體驗和讀中文小說蠻不一樣的。一方面是語言文法句型結構的不同塑造了不一樣的氛圍,一方面則是字的選擇(雖然我的單字量非常少,不過我遇到感興趣但是不懂的字都會去查一下)更是增加了另一個維度上的豐富性。舉個比較生活化的例子,把一本用英文寫的小說翻成了中文,就像是把一首鋼琴奏鳴曲編成了小提琴版本。的確小提琴還是可以把曲子演奏的很動聽,不過有一些作曲家想表達的細微想法可能要在鋼琴的演奏才感受的出來。

前言 - 科學研究的啟蒙與一些近期的體悟省思

看完《玻璃珠遊戲》之後,我對於科學研究有了全新的省思。科學研究是什麼?對於這個問題可能每個人的答案都會有些不同,在不同的人生階段可能也會有不太一樣的體悟。為了避免誤解其他人對科學研究的詮釋,就讓我講講自己在不同時期的理解吧!

相較於現在身邊的在各個不同科學領域中的佼佼者,我的科學啟蒙是相對非常晚的。從小我的父母很努力讓我在一個沒有太多競爭、能夠自由探索的學習環境下成長,而好動的天性讓我在大學以前把大半的時間都花在運動上面,學習對我來說就是個“國民義務”,而研究更是我從未接觸過的未知事物,只有印象某些同學會為了升學弄一些煞有其事的科展。

在大學的前三年,我開始接觸到一些比較有意思的知識,無論是數學之美、歷史的糾結、社會學的深刻還有哲學的富饒,在大學中傳授知識的方式和內容徹底的啟蒙了我對於學習的熱忱和好奇,也因此讓我很想要能夠一直待在這樣的環境中不斷汲取精神的養分。那要如何才能一直待在這樣的環境呢?在多方請益之下,我才發現,原來必須要“做研究”才能獲得留在學術圈的門票,然而到底什麼是做研究呢?對於當時的我來說(相信對於一般社會大眾來說也是),腦中浮現的就是課本上諸如愛因斯坦等偉大科學家,在黑板面前寫下一堆看不懂的公式,或是穿梭於冒著煙的各種不知名儀器。

然而身為一個電腦科學本科的學生,所謂的“研究”似乎又和想像中的很不一樣。身邊的同學有的成天在煩惱如何讓機器人踢足球,有的埋首於大型程式專案的開發,有的則是一天到晚在等機器學習的訓練結果跑完。對於熱愛抽象思考的我來說,這些怎麼看都跟我感興趣的知識扯不太上什麼關係,唯一一次讓我感到興奮的是在一個軟體工程的專題中,老師推薦我學習一些「設計模式(Design Pattern)」的概念然後應用到一個大型程式裡面。我十分著迷於設計模式裡面各種優雅的物件導向概念,但同時這些漂亮的抽象概念似乎又不是研究中的主角。

在大學的最後一年,我終於在繞了一大圈之後,如同一開始所料決定投身於理論研究。在台灣做電腦科學理論的人非常少,沒有什麼具體的研究問題可以做,身邊也沒太多人討論。不過這樣的環境反而讓我在這一年中可以非常自由的敞洋學習的大海中,讀了大量的研究論文和書籍,也寫了不少的筆記,現在回想起來實在是一段精神上非常充實愉悅的時光。

後來順利的申請博士班來到了Harvard,滿懷雄心壯志的想要繼續吸收各種知識,同時也期許自己在研究上可以做出新的貢獻。卻在時間一年一年過去後,才慢慢發現當初吸引我的那些知識和學習的純粹之美,竟然不完全是最前端科學研究的首要目的,甚至會被一些領域裡面汲汲營營於發表論文的人所不齒。我漸漸開始理解當年在科學哲學課上學到Thomas Kuhn對常態科學(Normal science)的批判,而近期看完的《玻璃珠遊戲》更是重重敲醒我的最後一根稻草,讓我又開始不斷的思考最根本的問題:科學研究是什麼?是為了什麼?

《玻璃珠遊戲》The Glass Bead Game

讀完《玻璃珠遊戲》後,那種思想上和精神上的震撼,絕對不亞於在大學時第一次接觸現代數學時的衝擊。醞釀了許久之後,遲遲找不到一個下筆的起點,因此我決定在不劇透的情況下,藉由引用書中的一些句子,來分享這本書帶給我的啟發。裡面的句子和頁數是來自於Richard Winston在1969的英譯版本,中文翻譯則是我的詮釋。

對完美與純粹的追求

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.

真理是存在的,我的孩子。不過你渴望的那種純粹、完美並且提供智慧的學說是不存在的。你甚至不應該期盼有個完美的學說,我的朋友。你應該追尋自我的完美,畢竟道理是存在你心中而不是在思想和書本裡的,就如同真理是被實踐而非教導的。Joseph Knecht,準備好面對衝突、矛盾與困惑吧,我可以看到一切已經開始了。

Page 83.

身為一個極為幸運的人,從小除了一些家庭經濟上的煩惱之外,父母總是給我很大的自由去跟著直覺還有興趣選擇人生的方向,因此我的生活一直非常具有理想主義的色彩。在上大學後開始接觸許多被包裝良好的各種學說,更是加深了我對完美以及純粹的追求。大概是到了讀博士的第三年,我開始接觸一些跨領域的研究,漸漸認知到純粹理論和現實的巨大鴻溝。尤其是在認真的思考生物學的問題之後,更是讓我懷疑這世界上是不是沒辦法有完美解釋一切的理論。在這段期間我的思想被劇烈的撞擊,這感覺大概就像從小的信仰受到了挑戰,發現這個世界可能沒有當初想像的這麼美好單純。

相信存在完美純粹的學說是個浪漫的選擇,或者說這也許是個比較輕鬆的選擇。如尼采說「上帝已死」,對信仰開始產生懷疑甚至將之拋棄,是選擇走向一條即將充滿衝突、矛盾與困惑的路,不過這可能才是通往真實世界的路吧?

知識、生命以及存在的價值

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.

這一段文字,可以說是切切實實的描述了我在疫情這一年的生活寫照。隨著在學術界越待越久,研究經驗和成熟度也漸漸提升。但也因為更深的理解,反而對於研究內容的意義產生了更多的懷疑。多做出了幾個“研究結果”,除了對領域內少數的專家之外,還有什麼其他的價值?當我試著很誠實的去回答這個問題,就會發現主要的價值似乎是在讓自己開心,這之中包括滿足了好奇心、解決問題的成就感、研究結果和能力被外界認可的虛榮感、研究所產生的一些價值感等等。

其實,在想這些關於價值的問題,也不是說做研究沒有實際價值云云,而是在想當一個科學家犧牲了生活、家庭、健康等等造就傑出的科學貢獻,這是我所追求的價值嗎?如果是的話,那為什麼有時候心裡會感到如此的掙扎難受?又或是研究帶來的喜悅不如從前了?價值並不是一個絕對的度量,而是隨著時空不斷變化調整,要如何知道自己的價值觀正在漸漸的改變?要如何面對自己價值觀的變化?

懷疑所學之物的意義

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.

對那時候的他來說,最重要的就是一切關於玻璃珠遊戲的學習。不過那時候一直有個問題纏繞在他的心頭上:玻璃珠遊戲真的就是Castalia裡最至高無上的成就嗎?玻璃珠遊戲真的值得一個人奉獻和投入他的一生嗎?即使他正在讓自己從遊戲的規則和可能性中熟悉越來越深層複雜的謎團,即使他漸漸熟稔檔案館中曲折的迷徑以及遊戲符號裡複雜的內部世界,他心中的質疑從來沒有安靜下來過。從經驗中他已經學到信念與質疑是共存的,它們如同吸氣和吐氣般互相支配。而他對遊戲裡各個層面最尖端理解,更是引領著他直視著遊戲中所有令人感到可疑與不安的地方。

Page 134.

在上一個段落我們討論到了知識的”價值”,在這一段文字中主角更是開始思考所學之物的”意義”。聽起來價值與意義好像是差不多的東西,不過仔細想想的話,價值是指比較客觀物質和感官層次的感受,而意義則更是帶有主觀精神和情感的寄託。就像當你評論一個科學家的研究或是一個藝術家的作品是毫無價值的時候,雖然否定了客觀的實用價值,但是對於他來說,自己用心血做出來的研究和作品是有特殊意義的。

一件事情可以是非常具有價值,但是沒有意義的。舉個極端的例子,一個偉大的棒球員在職業生涯中創造了無數的紀錄,在許多球迷心中留下深刻的美好回憶。但是他其實一點都不喜歡棒球,甚至因為童年嚴酷訓練的陰影而討厭棒球,他打球純粹只是因為自己有天份,而且能夠養家糊口。棒球還有他的職業生涯對他還有社會來說是很有價值的,然而對他來說這卻是沒有意義的,畢竟要不是因為他只會打棒球,他還寧可去當個廚師還比較快樂呢!

意義是個比價值還要更飄渺不定的概念,而同時人們對於意義的追求時常是高過於價值的(或是人們會不自覺把價值轉變為意義)。要一個人做件對他來說有價值但是毫無意義的事情是可以非常痛苦的,但是如果事情對他來說是很有意義的,即使沒有具體的價值,還是可以甘之如飴。在這種情況下,意義儼然對他來說是非常具有個人價值的,而從古至今許多藝術家甚至是科學家的例子也讓我們看到,時間有時候會改變社會對於價值的判定。

不只是價值,意義也可能會改變的,就像這段文字中主角內心深處對所學之物的質疑。我覺得最精彩的地方,就是作者刻畫了主角因為對玻璃珠遊戲更深刻且更尖端的理解,反而產生了更多的懷疑。這可以說是一種智識上誠實(intellectual honesty)究極的展現,更是敲醒了我心中一直沈睡的不安。對於我自己的領域,一直以來我都十分的享受學習還有做研究的過程,然而這一兩年來接觸越來越多其他的領域之後,心中開始浮現一股難以言喻的擔憂(也許在這篇之前的文章中就開始醞釀了)。當然,領域本身沒有什麼太大的改變,對於其他人的意義來說應該也沒什麼變化,但是因為我的成長和見識上的開拓,我開始需要好好重新思索所學之物對我的意義是什麼了。

純粹與抽象的烏托邦

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.

同時我們更加深入了純粹心靈的境界,或是換個說法,純粹抽象的世界:在我們的玻璃珠遊戲中,我們分析了智者還有藝術家的作品,從風格還有結構中推導出規則還有模式,並且把這些抽象過後的概念作為一個個小元件般地操作。當然,一切都是非常精緻的,這是沒有人會反對的。然而,並不是所有人都可以把吃喝拉撒睡都捨去而一生中只活在抽象之中。歷史學有個超越Waldzell導師會感到有價值和興趣的長處:它關乎於現實。抽象當然是沒有什麼問題的,不過我覺得人們還是應該呼吸些空氣還有吃些麵包。

Page 279.

最近和室友看了部美劇『上載新生』(Upload),在講述未來的人在死後可以把靈魂上載到一個雲端伺服器繼續過生活。光是從這個設定,就可以想像有許多有趣的故事和問題可以發展,而編劇和導演也的確把整部劇拍的引人入勝。如果在未來這樣的科技出現了,你會想要把自己”上載”,然後從此過著不受物理和生理限制的生活,可以盡情做喜歡的事情嗎?

某種程度,玻璃珠遊戲裡的Castalia(一個書中所有遊戲大師聚集的地方)就像是個伺服器,在之中的所有人只要專注在玩遊戲還有怎樣變更厲害就好了,不需要煩惱一切其它世俗、現實與過去的問題。同樣的,在我們所處的世界中,有些領域也或多或少進入了這樣的境界,沈醉在純粹與抽象的美妙中,如同魏晉時期的清談玄學。作者的這段話,可以說是對這樣的風氣做出了委婉但深刻的批判。

關於這段話,我覺得挺有意思但是一直沒有想得很明白的是:為什麼作者選擇了將玻璃珠遊戲和歷史學做比較?尤其是”it deals the reality”想表達的是什麼意思呢?對於現在以及未來,歷史發生在過去,於是就像抽象的世界一樣不再是真實地存在於當下。歷史學研究的是過去的人物與事件,如果有現實價值的話,大概也就是所謂的見古知今了,在這方面的確又和純粹抽象的學科十分相似。但是和純粹抽象最大的不同就是,歷史至少曾經是真實過的,而抽象的學科例如數學和哲學雖然有很多實際的應用,但本質上是存在於純粹的烏托邦。

其實在書中作者並沒有明確地提及”烏托邦”,不過我刻意在這邊稱呼純粹抽象的世界(諸如書中的玻璃珠遊戲,或是數學和哲學等等)為烏托邦,是因為在這樣抽象的世界中,我們基本上都只思考著完美理想的層面,換句話說更像是一種對現實的逃避。有時候我們甚至會過於著迷於之中的美妙而忽略了現實,甚至鄙視現實的醜陋。然而reality is real,我們不該忘記我們終究是活在這個世界上。不過也許幾十年後,科技進展到可以實現『上載新生』裡面的設定,那麼也許抽象將成為新的真實?

在社會中的角色

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.

嚴格來說,那些在外頭的老師才是我們之中唯一傳遞Castalia真正意義的人。透過他們的工作,我們償還了國家給我們的各種特別待遇。在領導階層中的每個人都知道,我們至上且最神聖的任務就是要保存國家和世界上的一切知識根基。而這些基礎價值成了道德上的元素,並且很有效的督促我們執行使命,其效力不亞於其他諸如法律等等所依賴的主觀事實。但如果檢視我們真正的想法,大多數的人都會承認,我們並不把外頭世界甚至我們小小國度內的福祉當作最重要的事情。事實上,這些對我們來說完全不重要,我們非常樂見這些勇敢的老師們在外頭犧牲自己,償還我們虧欠世界的債務。我們這些玻璃珠遊戲玩家、太空人、音樂家、數學家,甚至以這些來合理化所享受的一切特權。就是上述的這些自傲與階級意識,使得我們不在意我們的貢獻是不是真的值得這些特別待遇。就算我們因為領導階層的限制而過著節儉的生活,我們之中絕大部分人卻是沾沾自喜地將此視為一種自身的美德,而非將此視為我們回報國家的最基本方式。畢竟,是這個國家才讓我們這些Castalian有機會存在的。

Page 350.

還記得當年在中研院最一開始帶我的一個博後,在他當上教授拿到傑出教學獎的時候,在Facebook上寫到:他們系上的一個資深教授,曾經在他剛入職的時候告訴他,「教學才是當教授的本業,做研究是輔助和附帶的。」我一直覺得這句話很耐人尋味,尤其是在這個故事中更顯得有種傳承的色彩。到底作為一個教授,或是學術機構的一個研究員,肩負的天職是什麼呢?做出頂尖研究和指導後輩傳承知識,哪個更為核心?

一般的論爭也許會把這個問題作為二分法來討論,有些人擅長研究有些人擅長教書,同時兼顧的可能是少數,甚至大部分的人在兩個方面都不太及格。不過如果仔細想想,做研究的核心不也是傳承知識嗎!?所有研究都是建立在溝通和傳遞上,從一開始被領域內的專家認可,然後也許開始有些follow-up的研究,有些開始影響其他領域,有些甚至被寫進教科書,最終慢慢回歸這個社會,流入歷史的長河。

所以對我來說,研究其實是教學的另一種形式,其根本還是在於知識的傳遞,而身為學術界的一員,我們的天職就是在學習、發現和傳遞知識之中不斷循環。在這段節錄的文字中,作者對只注重於學習和發現的”玻璃珠遊戲玩家”,做出了非常銳利的批判,這未嘗不是暗諷學術界的部分現況?不過平心而論,這還是個適者生存的世界,每個人有自己的選擇,過多的批判有時可能只會造成反感和反彈,身為一個小小博士生,我只期許自己能夠將這些本質的價值和意義牢記在心中。

覺醒與真實

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.

我總覺得,人生就是個持續的覺醒與認知真實的過程。想想第一次吃到美味的生魚片、第一次聽到美妙的音樂、第一次被數學證明感動、第一次登上山頂眺望整座城市,在經過一些事情後,我們看世界的角度就變得不再一樣了。當眼界和見識被打開之後,就很難回去當初單純的狀態,胃口變得越來越難被滿足、開始聽得見音樂中細膩的巧思、追求抽象思考的極致、嚮往走遍世界的每個角落。覺醒可以有大有小,通常讓人在當下沒有太大的感覺,是在累積了一定的程度之後,才突然發覺自己好像跟以前有點不一樣了。

而有些覺醒則是會讓人徹底的改變價值觀,就像在啟蒙時代的人們,從宗教和感性走向科學與理性。在這段自白中,主角更是用誇張的例子強調覺醒中的真實帶給他的劇烈衝擊。同樣的,看完《玻璃珠遊戲》之後,我也經歷了類似的覺醒體驗,在看待研究或甚至是生活中的事情時,我開始會想一些以前沒有想過的層面,給事情賦予的價值也開始轉變。回頭看看幾年前的自己,突然會有種陌生感,很訝異當初的自己怎麼會在意那些事情、犧牲了這麼多其他的人事物。

是夢還是真實
或醒亦或沈睡
無盡的黑夜 風輕拂著
刺眼的白晝 萬物蒸騰
擺渡的船呀
要在哪靠岸?

後記

《玻璃珠遊戲》讓我最佩服的一點就是,作者雖然滿腹想法要告訴讀者,但是他不是用說教式的方法直接說破。而是藉由主角的成長歷程,慢慢讓這些想法自動地從讀者心中產生出來,讓人一讀就感覺到,「啊,怎麼把我心中模糊的感覺和想法都寫出來了!」甚至在故事的結局,也是在倒數幾頁時就開始讓我隱隱有種預感,而最後作者用美麗流暢的文字,將原本應該令人意外,但卻又意外地用讓我不意外的方式,留下意味深長的詠嘆。

回到最一開始提到科學研究之於我的意義,我想與其再多幾千字的論說,不如就用上面這六段讓我特別有共鳴和感覺的文字,讓讀者猜一猜、想一想、體會一下我的覺醒時刻吧!

(感謝Brabeeba Wang和Wei-Chung Lee對於文章的許多好建議!)

Littles

前陣子看了一部香港的排球電視劇『男排女將 (We are the littles)』,本來只是吃飯時跟著喜愛排球的室友一起打消時間,沒料到隨著劇情的發展,當年打棒球的種種回憶漸漸湧上心頭。看著主角們對於排球的癡迷,就像看到五年十年前的我還有當時的隊友,躺在集訓室擁擠還帶有奇怪消毒水味的上下舖,即使隔天六點就要起床練球,還是在睡前興奮地討論要怎麼練球、怎麼打贏大專盃…

這部電視劇如果不是香港人或是熱愛團體運動的人,可能不會覺得有什麼特別之處,畢竟既沒有錯綜復雜或是感人肺腑的劇情,演員基本上也是素人(另外一個選秀節目出來的)擔當,專精排球的人甚至還會覺得他們球也打得不怎麼樣。不過會讓我漸漸產生強烈共鳴的反而就是這部劇的單純和寫實,看到非主力球員對於自我角色的懷疑,看到主角之一由於身高所限放棄熱愛的主攻手轉為自由球員,看到教練因為球員之間的不和忍痛將主力球員禁賽。這些情節都曾經在我國中和大學這兩段棒球生涯中出現過,當時的困惑、不平、失望,現在從第三者的角度看了格外感同身受。

而當年的劇情沒有像電視劇一樣過關斬將,可能我們(尤其是我)遠不及劇中角色的認真堅持,國中的時候在最後一年放棄了朝職業球員邁進的夢想,棄武就文。大學時又重回棒球的懷抱,加入了校隊,然而在成為主力後卻又連續兩年在複賽就被淘汰,當初同屆一起加入球隊的九位隊友更是相繼退隊了一半,我也在大四暑假前經過幾番長考後再度放棄了棒球。

一直以來,我都是用自己打棒球沒有讀書一般的天份,來說服自己做出放棄棒球的決定。但是在看到劇中的主角不斷的突破自己的極限(不像動漫,電視劇是真人演的,有幾個演員是真的把排球練到一定的水平了),我開始反思當年的我真的有盡力了嗎?再想起當時幾個特別瘋狂的隊友,整天嘴上都掛著棒球,吃飯時討論晚點要去健身房重訓,搭捷運時還不忘練習揮棒動作的轉腰。反觀我當初還常為了學業或是其他的社團活動想辦法減少訓練。我實在忍不住問自己,還是其實我根本沒有這麼喜歡棒球?

甚至不說棒球好了,我是不是也沒有這麼喜歡我現在的領域還有我的研究?我是個對很多事情感興趣且有行動力的人,但是總覺得在每件事上面好像都少了些什麼。國三那年放棄棒球後,我沈迷了速解魔術方塊了好一陣子,一度練到平均12-13秒,但自此就是無法再進步了,於是升上高中後也漸漸把方塊們收進了櫃子裡。在大學的後期逐漸體悟了數學的有趣及浩瀚,自此不知道多少次想要好好的學習某一個數學的分支,整理自己的筆記,每次都毫無例外的進行了幾個禮拜幾個月後就無疾而終。

在劇中令我非常印象深刻的一段,是主角因為跳高的極限,在嘗試了很久之後最後決定放棄主攻手,他當時說了一句:「既然喜歡的事情不是自己擅長的,那不如喜歡上自己所擅長的吧!」我喜歡的是什麼?我擅長的是什麼?我覺得我喜歡的是學習各種有趣的事物,連在專業領域上我也是涉獵非常廣泛,而我的確也還蠻擅長很快的學習新的知識或技能。但是我一直以來也知道自己很有障礙把一件事情做得很深,我總是在開始熱衷學習某件事情一陣子之後,就又被吸引去學習其他東西了。也許有些事情做的稍微深入一點,像是棒球或是我現在研究的領域。但是跟同件事情的專家比起來,我根本就什麼都不是,充其量就是玩票而已,甚至距離我期許自己的程度都還很遙遠。

也許我該面對自己這樣無法把一個方向走很深的現實吧!?就像一個合作者曾經跟我說過的,我這種觸角廣泛的人在初期可能走的比較慢,但是未來的路可能可以走得更遠更寬廣。只不過每當不經意滑到棒球的影片時,內心還是會被輕輕地觸動一下,閉上眼想像如果當初再多堅持一下,球從指尖滑出的刺激,球棒擊到阿答力的暢快,還有撲球時球進入手套的那個撞擊。我想我還是知道自己喜歡的是什麼吧,只不過很可惜那不是我擅長的。

Ph.D. 第三年心得

(See here for an English version)

立秋過後一週,新英格蘭地區的酷熱終於得到(暫時的?)緩解。也不知道是今年真的比往年炎熱,還是長期的隔離讓時間感覺過得特別慢?突如其來的疫情改變了生活,也改變了對時間的感知,秋天即將到來,也意味著又是一個學年的結束。

相較於前兩年迷茫的探索,第三年博士生的日子則像是在看到一些方向以及得到一些成果後,感到更加的迷茫了。不過迷茫也許沒有聽起來得那麼負面,畢竟在Harvard校園隨便攔個研究生,我相信大部分的人也都會說自己很迷茫。所以重要的可能是要知道自己在迷茫些什麼吧?前兩年的我主要是對於自己能力上的懷疑,而如今在跨越Ph.D.的中線之後,不斷在我腦中思辨的是什麼樣的研究方向(甚至生活方向)是我所追求的。

不過anyway,在比較嚴肅的討論前,先來回顧一下這一年發生了些什麼事情吧!

這一年做了什麼?

去年的這個時候,在幾番思考後,決定除了在我主要的領域complexity theory之外,多花些時間探索和theoretical neuroscience相關的研究。因緣際會之下,和在MIT讀Ph.D.的好友Brabeeba展開了合作。連續幾個月我們密切的在MIT學生餐廳、Harvard的宿舍甚至還有波士頓交響樂團的音樂廳進行大量的討論,最終我們不但成功的給出了第一個biologically-plausible learning rule的convergence rate分析(link),相關研發出的技術,也讓我們有了些後續的有趣延伸作品(link)。

這次和Brabeeba緊密的合作經驗,除了帶給我更多在研究上的自信之外,也在如何與人合作上面獲益良多。Brabeeba和我在研究風格上非常的不同,不同到幾乎是完全的互補。在好的時候,這樣的互補可以讓研究進展得非常迅速,因為每次我卡住的時候,Brabeeba總是會有些新的idea,而當Brabeeba覺得遇到dead end的時候,則是換我開闢出另一條道路。然而這樣的互補關係在遇到不同見解的時候,尤其是在寫作的部分,我們總是爭的互不相讓。不過幸好我們之間一直有著很良好且直率的溝通,最後通常可以把爭執點轉為前進的能量。

而在complexity theory相關的研究,雖然在大部分感興趣的方向上仍然毫無進展,不過至少在一個方向上有了一些突破。一切的起點是個聽起來很簡單的問題:在只有logarithmic space並且1-pass的情況下,可以多好的approximate一個directed graph的最大directed cut?之前的研究發現了比trivial做法還好一點的(2/5)-approximation,然而另一方面,大家只知道(1/2)-approximation是達不到的。在和SanthoshiniSasha的合作之下,我們發現了(4/9)-approximation才是最終的答案!並且透過相關的技術,我們徹底的分析了所有boolean 2CSP在streaming model下的最佳approximation factor(link)!到了暑假的時候Madhu加入了我們的討論,又更把這方面的研究往前邁進了好多步(Update: link)。

此外,在和Boaz還有Xun的合作中(link),我們試圖挑戰google的quantum supremacy實驗。起初Boaz和我有個簡單的classical algorithm,不過在分析上一直不是很理想,直到和Xun聊過之後,發現在理論物理常用的tensor network技術可以很直接地給出嚴謹且理想的分析。而在後續的研究中,由於在純理論的分析上會有些本質上的障礙,於是我們使用了部分理論、部分數值模擬的方式來論證我們的演算法效果。

這樣的研究方式帶給了我極大的衝擊,以前的我總覺得,如果不能從頭到尾用數學嚴格論證的就不是理論研究。然而在這次和理論物理學家合作之後,才讓我感受到與其在加了一堆假設後硬推出很鬆散的理論證明,可能不如部分理論、部分實驗來得有說服力。不過這當然還是要看想要解決的問題是什麼,如果是個本質的理論問題,那對於數學嚴謹度的要求當然是必須百分之百,然而如果是在探討更實務或是跨領域的問題時,也許理論與實驗之間的美妙平衡能夠提供更多且更深入的insight。

新的迷茫?

這一年下來做了三個很不一樣的方向的研究,很幸運的都有些產出,讓我對自己更加有些信心。不過接踵而來的則是對於未來方向的思考,一來是時間上的分配,總是得在這些不同的方向中分出優先順序,二來則是在接觸不同的研究方法後(e.g., neuroscience和物理),讓我開始回過來思考什麼樣的研究是我追求的、欣賞的。

在很多時候,complexity theory的問題雖然非常的吸引我,但同時也會讓我有種這就只是個intellectual game的空虛感。雖然說到底這可能就是純理論研究的矛盾/悖論之處,一方面如果只看大問題而不踏出微小的一步,可能會永遠踟躕不前;另一方面如果都把時間花在做微小的改進,可能花了一堆時間,卻還是沒有碰觸到根本的問題。然而一直陷在這個悖論中也不是辦法,我想我能做的大概也就是定期省思一下,到底complexity theory之於我是什麼吧,是一個證明自己intellectual power的舞台?還是承載著想要解決根本問題的使命感?

也因此在年初的時候我開始有了想再念一個數學Ph.D.(in Algebraic Geometry或相關領域)的想法,主要是在接觸了更多數學之後,深深覺得還有太多深層的數學沒有被拿來思考和complexity theory的關係,而且學習這些數學需要有對的“語言”,如果我在這樣順順走下去,是沒有機會好好的把這些語言學好的。就像是想要把英文學好,如果是在一個非英文母語的環境之下是不太可能的。不過話說回來,再讀個數學Ph.D.只是其中一種可能辦法,也許還有別的更好的方式?總之現在決定還太早,可以等到明年這個時候再來煩惱…

面對未來

人總是不停地在變,這大概是我這幾年來最大的一個醒悟了吧。變的可以是在能力上、視野上,也可能是在性格上、價值觀上,而這就告訴了我們當下覺得未來想要的,並不見得會是未來的自己真正想要的。以我自己為例,說來好玩,當初我會往學術界走的原因其實也不是因為喜歡做研究(畢竟我跟大部分的人比起來,是相對很晚開始接觸做研究的),只是單純對於學習很感興趣,而乍看之下學術之路似乎是個可以讓我開心終身學習之路,於是就這樣誤打誤撞走了下來。運氣很好的是,在多年下來之後,我發現自己很享受在做研究中探索未知的感覺,尤其是好幾個研究最後的結果都和一開始預期的很不同,讓我被這種神秘感深深吸引。而在研究方向上更是如此,在一年之前根本無法預期現在的我竟然在思考這些研究方向,同樣的現在的我大概也無法預測一年後的我在做些什麼吧。

幾個禮拜前,在一次散步中,我跟Boaz說最近我感覺遇到了career crisis,覺得不知道要往哪個方向走,不知道自己這五年十年要往哪裡發展。Boaz的回答很簡單,對我來說卻猶如醍醐灌頂,他說你就先好好想想接下來一年要做什麼就好了吧!也許是因為在讀博士之前的路,都有太多人的例子可以參考了,所以總可以先規劃好未來的計劃,然而真的到了獨立研究的階段時,每個人都必須開創自己的一條路,也許有些人可以往後看到幾年的發展,但是在大部分的情況下都是走一步算一步的。畢竟每個人都在變,這個世界也在變(e.g., 突然就來個pandemic),所以除了思考未來之外,很重要的一個能力是在每個當下找到好的方向,全力以赴,這大概除了做研究之外,在其他的人生課題上也是如此吧。

很多時候有些朋友總叫我別想太多,的確這樣做也許會讓自己少些煩惱,日子過得更開心點。不過至少對我來說,多胡思亂想通常能讓我更加知道自己到底想要什麼。畢竟日子還是要開心的過,然而什麼是讓自己開心的有時候並不是想像中的那麼明顯,說不定答案就是藏在胡思亂想產生的迷茫之中吧!?