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

The Glass Bead Game

(中文版原文連結)

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-fiction, 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 could easily get books in Chinese. However, since the never-ending pandemic started, my stock of Chinese books has run out, so I have no choice but to start reading English books, albeit slowly.

I’m not a person who reads a lot. On average, I read about 10 to 20 books per year, and every day I probably only read for 30 minutes to an hour before going to bed. Especially since 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 it took 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 will probably take me another two to three years to finish the original version of the book… But anyway, before sharing my thoughts on the book, I must say that reading an 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 another layer of richness and texture. Let me make an analogy: translating an English novel into 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 undoubtedly 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 of 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 exercise. 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 years of my undergraduate study, I started to get exposed to some interesting knowledge, including the beauty of mathematics, the complexity of history, the profundity of sociology, and the abundance of philosophy. The way knowledge was taught and formed completely opened up my passion and curiosity for learning. This made me really want to stay in such an environment so that I can keep consuming these mental nutrients. 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 people), the pictures in my mind were of great scientists like Einstein sticking out his tongue while 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 work hard all day trying to make a robot play soccer, while others bury themselves in gigantic programming development projects, and still others are always waiting for the training of their machine learning models. To me, as a person who loves abstract thinking, none of these seem to be the knowledge that I am interested in. Probably the only time I found excitement was in a software engineering project where the professor recommended that I learn 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 fulfilling 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. Year after year, 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 on 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 the philosophy of science. The recent reading of The Glass Bead Game was the last straw that struck me on my head. All of 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, the 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 fortunate person, except for some financial pressures from my family, my parents have given me great freedom to choose my life path according to my instincts and passions. As a result, my life has been filled with idealistic colors, and I care very little about practical affairs. After being exposed to knowledge from all those nicely packaged disciplines, the pursuit of perfection and purity has become even more deeply ingrained in my mind. It was around the third year of my Ph.D. when I started to explore cross-disciplinary research and became aware of the huge gap between theory and reality. Especially after delving into the questions in biology, I began to doubt the belief in the existence of a theory of everything. My philosophy was seriously challenged. It felt like learning that Santa Claus is not real and realizing that the world is not as simple and beautiful as I imagined.

Believing in 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 fights, conflicts, and confusion. But perhaps, this is the only road that leads 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. However, it is the deeper understanding of the field that has given birth to doubts about the meaning of research. Outside the experts in the field, what is the value of obtaining a few more “research results”? When I try to answer this question honestly, I realize that the main value seems to be my own happiness. This 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.

Reflecting on these questions about value is not a challenge to the real value of research but rather a self-reflection on what I really want. If I were to sacrifice my life, family, and health to make a significant contribution to science, is this really what I want? If so, why is there sometimes so much struggle deep in my heart? Or maybe the joy from research is no longer as strong as it was in the past? Value is not an absolute measure; it adapts and changes with time and space. How can I know if my own values are gradually changing and how can I face them?

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 latter contains subjective spiritual and emotional attachment. For example, when you criticize the research of a scientist or the work of an artist for having no value, it might deny the objective and practical value, but their research and work definitely have a 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 bad memories 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 society, it is meaningless to him. Perhaps if he had other skills, he would have been much happier being a chef rather than a baseball player!

Meaning is a much vaguer concept compared to value. Meanwhile, people often pursue meaning once they have achieved a certain level of value 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 value. 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. In this paragraph, the main character deeply doubts in his heart what he had been studying. I found this paragraph brilliantly depicts the main character having even more doubts after having a deeper and better understanding of the field. This is such an ultimate demonstration of intellectual honesty that woke up the anxiety in my mind. For my own field, I have enjoyed both the learning and research process very much and still do so nowadays. However, after getting more and more exposure to other fields in the past two years, there’s an indescribable concern arising inside me (perhaps this had been ideated since this blog post). Of course, there haven’t been many changes in my field, and its meaning to other people should not differ too much. But because of my own exploration and growth, I have to start rethinking about what the meaning of the thing I’m working on is.

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 the TV series “Upload” with my roommates. It is a story about people who can upload their souls 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 that 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, 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 a 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 with 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 Utopia of purity and abstraction.

In fact, the author didn’t explicitly mention “Utopia” in the book. But I purposely call a pure and abstract world (like the Glass Bead Game in the book or math and philosophy) as a Utopia. 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 reality. We should not forget that we ultimately 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 who once shared on Facebook, after receiving an award for 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 is their duty to 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 starting to influence other fields and some even being written into a textbook. In the end, it slowly turns back to the society and flows 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 society revolves around learning, discovery, and passing on 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 continuous awakening and recognizing the truth and reality. Think about the first time you had delicious sashimi, the first time you listened to beautiful music, the first time you were touched by a mathematical proof, or the first time you looked 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 expand, it is hard to turn back to the original simple mindset. Our appetite becomes more and more difficult to satisfy; we start to hear the delicate ideas in a piece of music, pursue the extremes of abstract thinking, and yearn to travel to every corner of the world. Awakening can be either large or small, but usually, people are not aware of it at that moment. After accumulating enough levels of awakening, we suddenly realize that we are no longer the same person.

Some awakenings can totally change one’s value system. For example, during the age of enlightenment, people walked away from religion and emotion towards science and rational thinking. In this confession, the main character from the book 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. Now, when I think about my research or things in life, I consider some aspects that I never thought about before. In particular, the meaning and value towards a thing begin 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 cared so much about certain things and why I sacrificed so much for 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 delivers dogmatic preaching on what he really wants to say. Through the growth and life path of the main character, these ideas naturally emerge from the reader’s heart, and one feels 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 conclude the story in a supposedly surprising but not-so-surprising way, like an everlasting hymn.

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