$
\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}
$
Visit Day @ Princeton University
08 Mar 2017
Princeton是理論CS特別是complexity theory的傳統強校，而且離高等研究院(IAS)距離十分鐘的車程，再加上位於兩座大城：紐約和費城中間的優雅寧靜區域，是個適合做理論研究地方。
參訪流水帳
Princeton是這次Ph.D.參訪之旅的第一站，也是來到美國後第二天的行程，就在還沒有很適應全英文的環境下，加上有點調過頭的時差，就在恍恍惚惚中從New Jersey的Bloomfield搭著姑丈的車子到了Princeton，一個充滿古都氣氛的小鎮。
第一天
第一天的行程只有晚上的聚餐，所以下午很愜意的在四點左右到了Princeton。在校園旁邊的Nassau Inn check-in之後，拿到了一個漂亮的package，很興奮地打開後，看到了
校園就如傳聞中般的漂亮，空氣很好，房子也不高，整個讓人有著很舒服放鬆的感覺。今天天氣其實還不算冷，大約十度上下，所以我穿得還有點太多，有些人就直接穿短袖在路上走，也有不少慢跑的人。
因為建築物都太美了，所以最後乾脆就不拍了，不然根本拍不完。而且Princeton這邊最令人印象深刻的還是還是整個氣氛，讓人很舒服自在，這是無法用圖片或文字記錄下來的。
回房間整理一下後就要去跟大家見面了，又是有點小緊張，之後大概還要再緊張很多次吧！一開始是在旅館的一個房間照領域分桌坐，Theory的有兩桌，看過去有超過十個prospective students，比想像中多很多。人種蠻均勻的，有不少印度人，也有幾個華人(望過去有一半是ABC吧)，另外也還有以色列人，歐美人等，也很不意外的只有我一個台灣人。基本上我的英文是最差的，光是要follow大家講的內容就有點吃力，說的時候也完全放慢很多倍速，不過他們是不會怎樣啦，頂多比較少問我問題，然後我比較難插上話而已。
後來幾個年輕的老師出現，跟大家打招呼，然後就一起出發去吃飯的地方。路上和兩個中國學生聊，雖然我還是用英文，不過跟幾個英文跟自己差不多破的人聊天還是比較親切的感覺。後來吃飯大家隨便分三桌坐，我做的這桌有四個印度人，一個ABC，一個以色列人，還有一個應該是美國人吧，其中兩個是就學的學生。運氣很不好因為我們這桌坐比較滿，所以教授都跑到別桌，我們這桌就只有兩個學生跟我們講講這邊的狀況，後來也都是某個Berkeley來的印度裔美國人東扯西聊一堆我不太熟悉的話題，我能聽懂就不錯了。吃的食物就是標準美式食物，一些炸的東西等等。後來陸續一些教授出現，看到平常在影片中還有paper上面看到的教授在眼前晃來晃去還真的是蠻令人激動的，更有種終於要來美國讀博士的感覺了。
八點多就一起去聽安排的一個演講，是某個教授(不是Theory的)分享他之前在白宮當科技顧問二十個月的經歷和心得，是還蠻有趣的，但是基本上也只能聽到一些無傷大雅的小八卦，所以後來有點無聊，我還打瞌睡了一下。九點半多終於結束，就趕快回房間休息了。
第二天
時差還是沒有完全調好，半夜兩點多有醒來一次，後來就睡到七點多。起床整理一下後，八點十五出門去系館吃早餐。一出旅館就有好幾個也是要過去的人，就一起走，然後跟一個很高的MIT學生聊了一下。這次visit day來的prospective students幾乎都是名校畢業的，MIT/Stanford/Berkeley/清華姚班一堆，隨便問幾乎都是前幾名學校上一半以上，爾且他們大多也都只申請前面幾所學校，所以之後的visit day應該就會遇到不同一群的人吧！然後發現非theory的master似乎還是比較多(姚班例外，他們根本就可以當研究生來看了)，theory的則大概一半一半。吃飯聽老師們聊天，他們說到即使有什麼數學競賽，沒有研究經驗他們也不太會收，而他們好像也不太會期待大學生有很多研究成果，像是我說到台大很多大二大三開始做研究他們也有點驚訝。像是一些美國top的學校像是Stanford/MIT還有以色列的大學部做研究的風氣好像普通，聽學生說好像他們比較著重在學習。
早餐是一堆美式食物，實在是很高糖分和高鹽份。結束後全部人到一個演講廳，先聽系主任介紹學校、系所、program，然後聽四個不同領域的教授小演講。很久沒有聽理論以外的CS演講，也是蠻有趣。十一點結束後就是各個領域的group meeting。theory group還是在同一個小演講廳，來了八個教授輪流五到十分鐘的簡單介紹自己的研究興趣，很theory風格的都是用白板介紹。每個教授講的方法很不一樣，比較多的是用一個簡單的題目來motivate研究的方向，有些就比較high-level，光是看教授怎麼快速present自己的研究興趣就可以感受到他們的厲害還有自己可以學習的地方。結束後就是午餐，跟早餐同一個地方，食物也就是那些類型的。同桌的有三個教授和三個學生，主要就兩個MIT的傢伙跟老師們聊天，我偶爾講幾句，後來有個旁邊一個Stanford的印度女生聊一下。一點吃完就開始一連串的1-1 meeting，每個教授的時間是二十分鐘。
第一個老師是Zeev Dvir，是做偏coding theory，特別是locally decodable code。聊到後來有點乾，而且其實他之前就講過自己的研究，所以有些時間是兩個人一起發呆。
第二個教授是Mark Braverman，講了很多我有興趣不過之前不知道的東西，主要是communication complexity和circuit lower bound之間的關係。他個人的想法是覺得大家實在對boolean circuit的了解太少，很少有結構性的東西被提出(大概就只有switching lemma和它的延伸版)，也許從communication complexity的角度來看會有些不同的機會。之後如果選Princeton會蠻想做做看這個方向。
第三個則是老教授Bernard Chazelle，和我的研究有點關係，不過他一副就是純聊天，而且感覺很熟練這種meeting，所以就都只有一些high-level得閒聊，他還說他覺得最好吃的中國菜是在台灣吃到的XD
第四個教授就是當初寫信給我的新教授Gillat Kol，跟她簡單講一下我的研究內容，然後聊聊Princeton還有聊要選Princeton還是Harvard。後來是個break，到tea room和這邊的學生聊天，不過主要也是聽他們聊，問幾個問題而已。後來他們要玩桌遊，結果是一個很吃英文的遊戲(codeword，一堆英文的單字卡，然後一個人一回合講一個單字跟一個數字，要大家猜出是哪幾張單字卡對應到這個單字)，我根本悲劇，像個智障一樣在旁邊…
四點再去跟最後一個老師meet，是做密碼學的Mark Zhandry，果然之前有接觸過還是有差，比較可以具體知道他在做的東西，他現在的focus是在iO還有multilinear map的安全性modeling跟證明，另外也有做一些quantum money。他是個蠻實在的一個老師，有機會的話也會想要跟他做做看，後來就跟那個老師邊聊邊走去晚餐的bar。
bar的食物也差不多，有個烤蝦子很好吃，不過很鹹，pizza也不錯。主要跟大陸人聊聊，其他的外國人實在差不進去，我真的就是個台灣來的小宅男吧。不過現在就覺得也沒有什麼好在意，就是不同的習慣，以後別人看你也是看實力，社交技巧也只是輔助，而且夠厲害之後，自然就會有人會想跟你聊天，以後待久了也慢慢會熟悉，所以現在也比較不會因為這樣的小事情困擾太久。
待了一個多小時後我就先回旅館了，休息一下，想說趁天黑前去逛逛校園，去找棒球場。不過球場比地圖上看起來的還遠，走到的時候已經天黑了，根本什麼都看不到＠＠倒是旁邊的美式足球場，燈火通明，根本沒有人在打球，實在超浪費的，美國人的style好像就是這樣，蠻奢侈的讓生活很舒服。而另外讓我蠻驚訝的是，這邊的車子都會讓路人，而且連續三次都是這樣，只要我在路口一副要過的樣子，車子就會停下來等我過，有點受寵若驚。
第三天
這一天已經沒有正式行程了，所以就很悠閒的體驗一下在Princeton的早晨，早上六點多就醒來了，繼續躺了一下到七點左右出門散步，往前幾天沒走過的方向。冬天的早晨十分舒適，不會到太冷，又有太陽。一路上人不多，偶爾有些路跑或騎腳踏車的人，還有一些要去上班的車。一路上彥霖用facebook和我討論一些問題，所以走走停停，後來坐在一個大草皮/公園/高爾夫球場旁的建築物前的長椅休息看風景。這邊什麼東西都很遼闊，很放鬆，眼睛也很舒服，難怪近視的人少。
做了一陣子後穿越大草皮/公園/高爾夫球場，經過一堆鵝旁邊，原本還怕他們會攻擊人，後來是多慮了。回到旅館附近也八點了，人開始多了一些。到主要的那條大街Nassau St.上的一家麵包店買了一個Pecan roll（灑滿核桃的甜甜麵包）和一杯espresso，然後走到附近的一個可以坐的地方吃。espresso意外的不錯，Pecon roll則跟想像的差距不大，後來吃了一半就回旅館了。
九點多離開旅館，把行李箱寄放，然後去附近走走。先去書店待了一陣子，買了一本書：Birth of a Theorem（之前看一個法國數學家2010年Fields medal得主Cédric Villani寫的，關於他做數學研究的探險歷程），還有三張明信片，後來就去找地方坐。好不容易打定主意去一家評價不錯但有點貴的cafe，結果爆滿，於是就改去附近的公立圖書館，免費桌子還很大。下午一點半多的時候姑丈和大表姐開車來接我，之前我先走路去郵局買個郵票然後把明信片寄出去，然後就離開這座美麗的小鎮，希望之後還有機會再來。
參訪心得
研究內容
Princeton CS這幾年開始要漸漸增加理論組的faculty人數，像是今年就多了三個教授，聽說目標是總共要多五到十個教授(目前有九個教授)。如果再加上IAS的的faculty，Princeton可謂TCS陣容最龐大的學校。這次總共和五個教授1-1 meeting，感覺上他們比較多的人是主力在communication complexity、information theory、coding theory上，特別是locally decodable蠻多教授有提到，前幾年STOC一篇best paper也是這邊博二學生和Zeev Dvir做的。此外，也有幾個教授做一些其他TCS的東西例如natural algorithm(不過感覺Bernard已經進入退休模式了…)、crypto(Mark Zhandray做一些蠻硬的數學，想要去定義還有證明multilinear map/iO的攻擊和安全)、algorithmic game theory(新來的Matt Weinberg在做，也有和其他教授合作，不過這塊我就不太懂)。
關於比較傳統的complexity theory，這次的感覺是教授們普遍認為很需要新的點子和數學工具，其實現有的招數都還是跳脫不出那些polynomial-based的工具，這大概也是有些人想要往communication complexity的方向找點子的原因之一。反倒是其他幾個領域例如crypto、game theory和theoretical ML看起來比較promising。大概是能用的東西還沒有被開發完全，有些地方是連分析的modeling層面都還沒有共識，所以還蠻多新的方向可以做。
這此比較可惜的是沒有問太多現在的博士生他們和教授互動的方式，不過大致上聽起來這邊的合作是比較緊密一些，各自教授間也常有兩兩合作，
與Prospective學生的互動
這次參訪Princeton遇到一票很猛的姚班學生，還有很多美國名校的碩士生。跟一些人聊研究的感想是，他們大多數都還是先從一個非常具體的問題開始，而且他們的指導老師也對那個題目有一定程度的了解和想法。而且其實和其他學生合作的情況也算常見。不過這些也都是建立在他們的基本能力夠好之上。像是MIT的CS學士其實數學的必修課程不深，所以理論的學生要嘛會雙主修數學，不然就是會多念個碩士。
而姚班是比較特別，他們其實前一兩年就已經有非常好的底子，甚至有些是高中就把大學前兩年的基礎課都學的差不多，所以很快就可以做研究。此外他們也有一些出國交流的機會，讓研究經驗更豐富。像是有兩個姚班今年大四的，剛上一篇STOC就是去UMich跟到超強老師，六個月就做出結果了。
所以根據這次的經驗，我會覺得研究和學習的分配是沒有絕對怎樣比較好，真的還是看個人的style，不過還是要適度的balance，或是起碼研究要有一定的經驗累積。
而關於研究本身，至少就大學部的專題研究來說，讓我感覺重點是在於了解做研究的整個感覺。對於理論CS來說，就是有survey相關研究的能力、清楚的定義問題、對於提出合適的問題有點sense以及對整個領域的philosophy有足夠的了解(至少瞭解到可以和教授溝通)。反而關於研究的本身，我認為第一個研究並不見得是要真的自己非常感興趣的(畢竟其實興趣也會轉變)，比較重要的是能夠讓學生從老師身上有效率的學習到做研究的過程，還有把研究累積的經驗。
而paper導向是好是壞，目前就感覺見仁見智，當然有paper是會多少幫助申請，但是沒有還是很有機會(像是我)。放長遠一點來看的話，最重要的我倒覺得是在做研究的過程中找到自己喜歡還有未來想要做的，不然其實時間過很快，到了Ph.D.差不多就該選一個方向好好鑽研下去。就這方面我是覺得還蠻慶幸我在臺大還有中研院的時候，除了自己的研究之外，也有涉獵很多不同的領域，至少就對下一步會比較有想法一點，跟教授們聊天的時候也比較有sense他們在幹什麼。
全英文環境的衝擊
這次二十天的visit travel是我有印象以來(或是說開始會英文以來)第一次到英語系的國家，所以去之前實在很panic，尤其是一想到在Austin要住在老師家就會腎上腺素爆發。雖然之前在台灣有不少和說英文的國人接觸的經驗，但畢竟是主場，隨便亂說別人還算會有耐心地去聽。到了美國後，一直很擔心的就是英文表達不清楚會遭人歧視(就像去上海的時候，說話偶爾會被另眼看待)。還好目前來看百分之九十九的場合下都還算可以，頂多有時候買東西吃的時候點A被誤認為是B。
不過在這邊還是感覺智商下降不少，吸收能力變慢而且反應力也變差。不過後來我再跟教授聊天的時候就試著放慢自己的速度，至少這樣講出來的東西比較有sense一點，而大多情況之下教授還是會等我一下，不過也不知道他們心裡怎麼想啦…很明顯可以感受出來即使在國內我的英文程度看起來還夠用，但是目前來講，英文還會是對於我未來的研究還有學習的一個阻礙，所以第一年除了好好學習和做研究之外，英文也是要趕快上手的一個項目。
總結
這次Princeton的參訪算是這趟旅程一個舒服的開端吧，無論是天氣還是和學生教授的互動。雖然如預期般的插不太進去別人的聊天，和教授聊天也沒辦法全部發揮，不過現在比較不會像之前太過度放不下了。一方面是亂想也沒用，另一方面則是其實最重要的還是自己的能力。就像一個教授說的，其實在理論CS，大家都蠻nice的，但是最終評斷一個學者優不優秀還是看你做了什麼。