$
\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}
$
2017 Ph.D. 申請心得
26 Mar 2017
從大三開始漸漸有了想要出國留學念博士的想法，經過一兩年在各個實驗室還有不同領域的歷練後，在大四的寒假下定決心要申請theoretical CS (TCS)相關的博士，並且目標鎖定在Harvard。從去年(2016)九月開始，與幾個同屆要申請的好友，還有許多學長、老師、家人的幫助之下，終於完成申請，並且熬過了痛苦的等待放榜的冬天，最終要如願在今年(2017)秋天到Harvard念博士囉！
首先放一些基本的申請資訊，最後面再講講我目前對於申請學校還有念博士這條路的看法。
申請相關資訊
申請結果
- Admission:
- UT Austin CS Ph.D. (1/29)
- Princeton CS Ph.D. (2/4)
- Harvard SEAS(CS) Ph.D. (2/9)
- UCSD CSE Ph.D. (2/16)
- Rejection:
- Stanford CS Ph.D. (2/4)
- UW CSE Ph.D. (2/4)
- GaTech CS Ph.D. (ACO program) (2/20)
- MIT EECS Ph.D. (2/24 on website, 3/31 via email)
- UCB EECS Ph.D. (3/3)
- Waitlist:
Decision: Harvard
背景
簡單介紹一下我的背景，我是2016年台大資工系大學部第二名畢業，輔系數學，領域是理論CS(Theoretical CS, TCS)，主要的興趣是在lower bound尤其是hardness of approximation。由於運氣很好在都抽到替代役入伍前一個禮拜發現符合資格可以當補充兵，於是除了十一月人間蒸發12天之外，其他時間是在中研院資訊所當RA。以下簡單列一下在CV上出現的一些條目。(大家可能會比較有興趣的是我在申請的時候沒有publication也沒有submission)
- Academic experience
- 台大資工+輔系數學(我數學課其實修很多，只是沒有被算在雙主修的學分)
- 中研院數學所暑期課程-密碼學
- 中研院數學所暑期課程-訊號處理與資料分析
- Research experience
- 現任中研院資訊所專任研究助理
- 電機系專題研究三個學期
- 中研院資訊所暑期實習生+一年的專題研究
- TA
- 資工系大學部必修-資料結構
- 資工系大學部必修-自動機
- 中研院數學所暑期課程-密碼學
- Awards and Scholarship
- 教育部公費留學數學科
- 五次書卷獎(前五學期)
- 三個校內獎助學金
- 某個創業競賽優勝
還有一個比較值得一提的是，我在大四那年參加台大一個主動學習者計畫，期間弄了一個TCS的部落格，然後還寫了一本中文的書。這個經歷收我的四間學校中有三間學校的老師非常emphasize，在他們寄給我的第一封信中都有特別提到，而且從信的內容可以看出來他們有真的點進去認真看過(有個Princeton的老師說他現在搜尋randomness extractors前幾個跑出來的結果中有一個就是我的XD)。當初參加這個計畫還有寫這本書本來只是興趣而且對於我自己的學習蠻有幫助，沒想到也在申請的時候有產生一些正面的影響。
申請必備資料
- TOEFL: 103 (R:28/L:27/S:22/W:26)
- GRE: 322 (Q:170/V:152/AWA:3.0)
- SGRE(Math): 870 (89%)
- SOP: 1100-1200 words (有趣的是，唯二有限制一千字以內的兩間學校都收我了)
- LoR:
- 中研院資訊所副研究員：一年大學部研究經驗，有一個即將投稿的研究
- 台大電機助理教授：一年半大學部專題研究，有兩個研究經驗，不過都沒有投稿
- 台大資工助理教授：修過兩門進階的課(上課人數都<=5所以跟老師互動很多)，且當過一門大學部必修的助教
準備過程
基本上我覺得可以把準備過程分為兩個部分，一個是申請資料還有考試的準備，這部分我大概是在死線前三個月開始弄，另外一個則是自我的認識還有養成，這個則是我大學四年都在做的事情，也是我覺得比較重要的部分。這邊先以比較standard的前者為主，第二部分會放在最後面給有興趣的人看。
申請資料的準備
英文的部分，我個人的態度是只多花時間在真的對未來有幫助的方面，如果只是純粹對考試是用的東西，我會盡可能不要浪費時間在上面。而且我覺得很重要的是，知道這些英文考試對你還有申請的意義是什麼，然後再開始準備。像我擺明了就是成績夠就好，考太高我還覺得浪費太多時間，所以我就盡可能只佔用閒雜的時間特別準備單字還有題目，然後寫一些題目發現大概可以過就不再繼續下去了。
看我的成績應該也可以知道我英文很普通，畢竟我從來沒有在英語系國家待過，高中英文也沒有特別突出。不過跟我同樣背景和能力的人相比，我覺得我的優點是在於我上大學後很強迫自己多找機會用英文，例如說只要可以用英文寫的作業我全部都用英文寫，其中包括了許多資工系還有數學系的project。而我也會比較偏好英文授課的課程(雖然很遺憾的我遇到的英文授課中有幾個實在教的很悲劇)，然後大四的時候有弄過短期的英文口說讀書會(每週一個早上六點起來和幾個朋友輪流用英文present一些主題還有討論問題)，也在中研院弄的讀書會全英文present還有討論。所以雖然我的英文稱不上好，但是算是很可以溝通。於是我其實除了背GRE單字還有考前一兩個禮拜寫考古題之外就沒有花太多額外的準備時間了。
為了要申請GaTech的ACO program，所以特地去考了SGRE的數學項目，最後考得很爛而且GaTech也沒上，所以大概可以當一個很好的負面教材吧。首先先說說我對這個考試的感想，蠻令我意外的是，跟那些general的題目比起來，我覺得SGRE數學還算有一定程度的鑑別力，題目難易程度的分布很均勻，雖然也是有水題但不會像，GRE的Q那樣讓人無言。雖然難題少了一點，但是因為他是用時間還有題目數量來換難度，所以個人覺得這比較是個測試熟練度和直覺的考試。
從考完的角度來看，我覺得最重要的是設定好你的目標，也就是只能錯幾題內還有如果時間不夠要放棄哪些類型的題目。像我就沒有設定好，當初想說錯十題內就好，後來才發現應該要設定個三題內比較實際。而且我一開始整個太悠閒，最後有四題還是五題直接空著來不及寫…
關於準備方面，看看強者我朋友的例子(大學幾乎沒修過數學系開的課)，直接以題目為導向來準備，一堆東西他根本原本不會，現在應該也是不會，不過他硬是考得比我這個修了十幾個數學課的人還高(不過還是要幫自己說說話，我修的大部分都是選修，所以對於分析還有幾何相關的必修是張白紙)。所以說難聽點，其實某種程度SGRE也像是個智力測驗吧@@我的心態則是，考前一個禮拜再開始準備(強者我朋友比我多一個禮拜)，於是最後一個禮拜開始每天寫五六小時的題目，然後盡可能地檢討不會還有錯的題目。
現在想想比較好的準備方式大概有兩種：第一就是像強者我同學那樣很暴力的在最後階段(視個人學習能力看長短)填鴨學習，第二就是大學的時候乖乖把那些必修課學一學，這樣基本上應該一個禮拜就夠了。因為我發現我最後沒把握還有跳過的就都還是那些我原本就不會的，也就是說根本沒有什麼準備到…不過話說回來，SGRE到底扮演什麼角色也沒人知道，因為我最後只有寄成績給GaTech。個人的猜測是，如果你沒有修太多數學系的課證明你的數學底子，那麼SGRE也許是一個證明數學能力的方式吧。
推薦信算是申請中最重要的項目之一吧！而基本上我覺得也是最單純的一個，基本原則就是找一個你覺得他對你夠瞭解，而且是個負責的人吧。此外，其實學生可以做的也不多，我覺得也不用太刻意要做什麼，就是好好的積極投入在研究或是學習上，累積一定的時間之後，就差不多是那樣了。比較要小心的應該是有些會雷人的老師，我是運氣很好沒遇到，身邊是聽過幾個例子很悲慘，有的是老師答應要寫，結果最後沒送，有的是指導老師拖很久，然後應該是沒有很認真的寫。
我個人的觀察是，一個老師平常做研究還有待學生的態度，應該會跟他寫推薦信的認真度呈正相關。也就是說，如果其實從平常的合作大約就可以揣摩出教授會不會認真寫你的推薦信了。因此，如果你感覺到教授怪怪的，也聽過許多閒言閒語，是可以認真考慮換實驗室，不然也不要太期待推薦信的品質了。
我準備SOP的方式基本上就是follow一個準則：「假想你是admission committee你會想看到什麼」。當然你畢竟不是，所以就要透過參考過去學長的SOP、請別人幫你看SOP、看別人的SOP等等來讓你有更好的sense去approximate教授想要看的東西。我覺得特別意外有不錯幫助的是看別人(一起申請的朋友)的SOP，正所謂旁觀者清，在看別人SOP的時候，通常比較會看出一些癥結點，無論是結構上還是內容上，而這些問題其實也很有可能出現在自己的文章中。但是因為每個人都對自己的SOP太overfit了，所以時常會沒注意到自己犯了什麼毛病，而透過看跟自己差不多程度的SOP時，在一來一回的過程可以一起成長。
而另外一個我的一個心得是關於細節與high-level的權衡。我個人認為，一個好的SOP，必須兩者都有，然後各自在適合的地方出現。如果整篇SOP都太細節，那麼很容易讓人看得很累，而且也比較抓不到最重要的部分在哪。而如果整篇SOP都太high-level，那有會顯得很淺薄，根本就像是加長版的CV。我個人的選擇是，在描述未來想要做的方向時是比較high-level一點的，畢竟其實老師們也不會期望你現在說一個方向，然後真的就五年往這個方向，他們最多就是看你對於這個領域的大方向有沒有sense。而對於自己的研究經驗，我就花非常多的工夫把細節寫好。
這邊說的細節並不是說像是寫paper一樣，而是講你做研究的過程，還有展現出你的熱忱。從我後來visit day的經驗是，除非你做的研究題目直接和老師的興趣有關，或是是一個整個領域well-known的題目，不然其實教授他們都不太會有印象你做了什麼。但是他們會提到的是，你用什麼方式來展現你的熱誠還有研究能力。
另外一個點是關於參考別人的SOP還有和別人討論SOP。我的心得是，大概找5篇左右的SOP來看就好，然後最好都是和自己領域幾乎一樣，或是至少大方向的性質相同。然後討論怎麼寫SOP的人也差不多在3-5人(這是指同屆要申請的)就好，畢竟人多嘴雜，其實大家都夠厲害，所以重要的反而是一起準備的人是不是真的願意用心一起看一起討論。而給老師還有學長看也是非常重要的一部份，而這也是要非常珍惜的機會，因為學長和老師沒辦法像一起準備的同學一樣花這麼多時間在你身上，所以你必須好好把握每次機會。我後期請教老師的時候，除了把SOP丟給他之外，我會先整理出我現在覺得困惑或是矛盾的地方，然後條列成問題，讓他可以很方便地回答。
寄信也許是在申請時最讓人困擾的事情之一，是一個感覺大家都在寄，但是又不太需要的東西。我當時也是問了幾個學長和老師，然後一直沒有什麼定論，而且這跟領域也很有關係，所以後來我在申請死線前都沒有寄任何信。不過後來在等放榜的時候，我想說Harvard如果我沒寄信結果最後沒有上，我一定會覺得很遺憾，所以就寄信給了我最想跟的教授，結果他半天之內就回信了，然後最後也很順利地成為他的學生。而另外我中研院的老師是有主動跟我說如果我有興趣的教授他剛好認識的話，我可以寫信過去然後cc他，他會特別在把我的推薦信寄一份過去，於是我就寄給了一個Cornell的老師，不過石沈大海，讓我很sad。不過後來在visit day的時候聽到八卦說可能要離開Cornell，因為在那邊待的不開心之類的，所以就有釋懷一點。
現在我的看法會是，如果你跟某個教授的研究方向很合，而且你也可以真的具體展現一些經歷讓他會感興趣的話，那是真的可以寄信看看。不過最好還是先跟同樣領域的學長還有指導老師打聽一下，這樣的行為在你的領域合不合適。
CS基本上面試很少(有些學校可能例外，像是CMU好像面蠻多的，不過我沒有申請)，而且基本上都只是一個check，所以有老師約說Skype聊聊，就放輕鬆，然後可以多準備一些研究方向上的問題吧。
不過在這邊還是簡單補充一些我和教授聊天的內容吧。差不多在一月中的時候收到教授直接回我當初寄給他的信，問我有沒有空Skype一下。因為擔心網速不夠，於是我跑到一個平常會開直播的學長家，後來的確很順利地在網路方面沒有出問題。當時教授沒有特別說約幾點，只有給一個時段，於是我就很緊張的在學長的房間等待，然後教授就突然打Skype過來了XD
一開始閒聊一下，主要是聊之前我線上旁聽他的一門課，還有我的一些近況。後來他就直接問我有沒有什麼想要問他。還好我有先想過一下，於是就針對我對他目前研究的方向上有興趣的部分問了一些，然後他就很興奮的分享螢幕直接講解給我聽。因為之前有聽過他的課，也讀過不少paper，所以大約聽八成懂，中間他隨性考我一個小問題，還好有答對。後來我有點問太多專業問題，他就問我有沒有除了學術以外關於Harvard的問題，我才回過神來趕緊問了幾個例如咖啡之類的東西。
總共大約快五十分鐘，基本上是個蠻舒適愉快的聊天過程，也沒有原本想的可怕，所以建議遇到類似這樣的面試，其實不需要太過緊張擔心，也不需要臨時抱佛腳，平常心面對，把你原本就想知道想要討論的事情拿出來討論就好了。
大部分的申請系統都還可以讓我們放一些補充資料上去，我雖然沒有正式的paper，但是有一些還算可以看的draft，所以當初就一直在掙扎要不要放上去。最後我只有放Princeton和Harvard，因為原本覺得前者一定不會上，然後後者想說不放最後沒上會很後悔。結果最後這兩間都上了！不過後來是沒有特別問說放draft在我的申請中到底扮演了什麼樣的角色，不過就結果論而言，放了似乎不是件壞事。
教育部公費留學
因為家庭因素，所以在大四那年去考了公費留學，也很幸運的錄取(數學科)，不過最終因為Harvard已經有提供全額獎金，於是放棄掉公費留學(這之間又發生一些曲折離奇的故事…)。以下簡短分享關於公費的經驗，還有一些給學弟妹的建議。
需不需要公費留學獎學金跟你的科系還有目標的學校很有關，像是我是CS然後又是讀博士，基本上根本不需要公費，當初獲獎後告訴兩位指導老師，他們都用很奇怪的眼神看著我，問我幹嘛要申請(我申請主要的原因是想讓家裡放心)。後來證明他們是對的，每間學校都有提供足夠的獎學金，而且基本上私立學校都不會讓你同時拿，或是說拿了也要用來付學費，這樣變成超級不划算。
最可怕的是，某些奇怪的學校規定還會不讓你放棄公費！沒錯，我就是在說Harvard，他們的行政人員竟然打算強迫我和台灣政府簽下賣身契然後把賺到的錢拿給根本不缺錢的學校。於是這讓我多花了將近兩個禮拜的時間，兩三天打一次電話跟行政人員吵架，同時寄信向Harvard的教授們求助，最後在4/15決定學校的死線前三天才收到更新的Financial offer，還多花了一千多塊用FedEx寄過去…
不過也是有例外的，UT Austin說可以讓我同時拿他們的獎學金和公費，因為他們認定只要錢不經過他們的手，就沒差。於是最後害我的選擇變成是一旦去了UT Austin我就瞬間多三四百萬…
以下的內容非常根據我的個人經驗還有領域，所以大家看看就好，相關的人想要知道更多可以私底下聯絡。
基本上數學科考的東西超級基本，所以我準備的方向大概就是，考前幾個禮拜把考古題寫一下，然後多練習寫中文字因為要考作文。我必須承認我其實第一階段沒有考很好，勉勉強強過去的，畢竟那些很瑣碎的微積分技巧還有在那邊算線性方程的解，實在無法跟年輕小伙子比呀！所以對於想要考高分來拉開距離的人來說，除了考古題之外，可能還要找一些以前的作業或是期中考題之類的來練手感，畢竟考試只能拿這種無聊的計算來測試。
面試應該是比較重要的，而主要可以分成兩個部分：基本的未來求學規劃和簡單的能力測試。
第一部分我覺得重點是知道自己的目標方向是什麼，然後想好一套說詞可以短時間告訴聽眾。尤其是我是做理論CS的，那些面試官要嘛是數學系教授，不然就是教育部官員，基本上沒有人很清楚知道我想做什麼。不過這看起來是壞處，其實也是個優勢，可以讓我講的很厲害很有前途，至少那些教育部官員很買帳。
至於能力測試，我被問了很基礎的問題：「state and prove 微積分基本定理」。這一聽就知道是要看看你數學的sense，所以我就刻意用比較基礎還有intuitive的方式來講，然後中途還試著要讓教育部官員知道我在幹嘛。雖然我相信他們應該是沒有懂啦，不過至少他們很津津有味地看我比手畫腳。
最後我的面試分數是85分，聽說就是比普通(80分)再好一點點的分數，看來面試好像也很難拉分。
有人說公費留學是你人生中第一個簽下的長約，要很審慎地看待。現在我的感覺是這其實是一個很彈性的東西。其實教育部的人就跟我們想像中的公務人員差不多，基本上就是來打卡上班，大部分對於教育或出國留學的理念等等都不太了解，也好像沒有很想要了解。所以一些原本以為很硬的規定，其實並不見得是這麼死。當然這是我個人biased的觀察，僅供參考。
還有一個讓我覺得很瞎的事情，就是在Harvard終於願意讓我放棄公費之後，我打去教育部請教怎麼放棄，那邊的大媽竟然也沒有跟我做身份確認，就直接說可以了。雖然說我和教育部只是簽了約還沒拿錢，不過看到他們這麼輕率地處理一個價值12萬美金的東西，讓我實在很汗顏。而且我最近還收到信提醒我要去簽約，看來他們根本沒有真的幫我放棄掉…
等待放榜
大概從聖誕節過完之後，到2/18收到Harvard正式錄取的消息之前，我幾乎是輪迴在一兩天睡不好半夜驚醒，然後再一兩天因為太累所以睡得很好。而且心情極度焦慮，很難靜下來做很多事情。主要焦慮的來源就是一種不確定感，不知道自己的申請條件到底在哪個水平，加上看到thegradcafe上面的一些不知道是真是假的消息。雖然之間有出去一日遊幾次，然後試著做一些比較不用動腦的事情來分心，現在回想起來，那段期間真的浪費的不少時間。
從現在的角度來看，我有些建議給以後再等放榜的學弟妹：
- 焦慮是正常的，大概我所有聽過的人都說在這段期間很忐忑，因次也不用想要強迫自己不焦慮。最重要的是不要過度焦慮，然後把緊張的情緒盡量轉為正面的能量。舉例來說，可以多去運動，或是出去一日遊等等，這些事情對於調劑身心還是會有一些些幫助，而且等結果都出來後，無論有沒有上學校，大概又要開始非常忙碌了，所以如果能在這中間一兩個月空下來的時間做這些事情，是還蠻一舉兩得的。
- 可以找些時間想想上了或沒上怎麼辦。
- 上了的話，你首先要面對的就是visit day，這個在下個段落會在特別強調，但是基本上你要對於自己想要做的事情有更多的了解，也要對於相關領域的發展有些概念，最重要的是你要想清楚你選學校的標準有哪些。
- 至於沒上的部分，當然就是要思考下一個年度該怎麼辦，你在這半年內有辦法讓自己的申請條件看起來變得很不一樣嗎？而心情的調適也是很重要，提早做好最壞的打算，可以幫助你在真的發生後快速地站起來。
- 不要太早開始刷thegradcafe，那上面太多莫名其妙在很早的時候都到AD的單一消息，而且其實大部分學校沒有面試也還算正常，所以能不要影響自己的心情就不要看(至少CS是這樣)。就我身邊大部分聽到的AD都是一群一群發，而且是在一月底二月初，所以我建議等那時候再開始看。
Visit Day
Visit day讓我對之後博班的規劃有了不一樣的想法，特別是關於學習還有做研究的balance，是經過和很多學長還有老師聊天後慢慢改觀的。簡單來說，現在覺得還是要以做研究為主，學習是比較個人還有要自己找時間完成的，主軸還是要在研究上面。
我有另外把參加visit day的心得還有遊記放在部落格裡，歡迎點閱。
對未來想申請理論CS的學弟妹的話
理論CS是一個在台灣看起來很不起眼的領域，但是其實在整個CS的領域中，還算佔了蠻重要的一席之地，畢竟一個頂尖的領域，除了heuristics之外，還是需要嚴謹的數學和科學方法才有可能走的長遠。舉例來說，美國絕大多數的CS Ph.D.都會要求至少修一門理論課，而且理論組通常都是前兩三大的組。也就是說雖然在台灣環境和資源很少，看起來很不熱門，不過在國外還算是有市場(就業就不一定了，不過visit完後聽起來是沒有學界還是不少可以進業界)。因此我會蠻鼓勵對CS有興趣又很喜歡數學還有理論的人，可以趁早嘗試接觸看看理論CS，而不一定要一窩蜂地擠去所謂當紅的領域。
小小推銷完之後，還是回到正題講講申請理論CS的Ph.D.的一些建議。和其他領域很不同的是，理論CS申請時看有沒有paper的比重比較輕一些，尤其是對於大學生來說，基本上如果可以透過SOP、推薦信還有一些輔助的資料讓教授看出你對作理論的研究有sense也有經驗，那麼應該是可以多多少少彌補沒有發表的缺憾。
除此之外，最重要的還是長期的累積。理論CS通常不像是某些領域可以很快的完成一個研究，有時候光是要了解一個研究的整個背景和脈絡，就需要非常多的閱讀和討論，因此這也是往往令人非常挫折和感受不到成就感的部分。不過這就回到了心態的調適，該如何在身邊的同學朋友發了好多篇paper的時候還耐著性子讀一些全台灣可能只有你會的東西、該如何在很多人不理解你研究的價值中繼續保有熱情。這些相信都會是在台灣做理論CS多多少少會遇到的狀況，所以遇到了並不用太氣餒，要知道有人曾經跟你一樣走過這段路。
基本上，當下定決心要走理論CS這條路，未來的目標就是往學術界前進了，所以把眼光拉長一點是可以讓自己更客觀理性的認知當下的處境。例如我現在就會給自己設定博士的前兩年先好好鑽一個方向，研究深入一點，把相關的背景、工具等等都內化，不急著要馬上就有產出，希望這樣可以讓自己不要因為眼前的競爭而失去了大方向。
數學的成熟度與研究的專業度
從學生的觀點來看，大概都會覺得申請時候最重要的就是有沒有好的研究成果/paper數量，或是GPA還有英文考試考得好不好。但是如果申請的是Ph.D.，對於教授來說這些可能並不是最重要的。以下針對理論CS這個領域的Ph.D.申請，加上根據我和一些老師(國內國外都有)聊天的心得，分析我覺得很重要的兩個要素：數學的成熟度與研究的專業度。
講到數學成熟度你會想到什麼？是像奧林匹亞競賽那樣？還是要修一堆數學的課然後拿高分？對我來說這是一個更深層的東西，如果要用一句話來說，那就是一種「能夠在抽象的想法與嚴謹的數學表達中來去自如的能力」。也就是如何從看似複雜的數學公式/證明中抽取出抽象的high-level概念，以及將抽象的想法具體的用數學語言精準的刻畫。
舉個可能比較多人可以感受的例子來試著解釋我想要說的概念，不過在這之前我必須先承認我的數學成熟度仍然非常不夠，以下只是我粗淺認知，歡迎大家多多指教。KKT conditions是一個(滿足某些regular condition的)optimization program最佳解的充要條件，書本和課堂上都會把那幾個條件(gradient為0, complementary slackness, feasibility)列出來，並且提供完整的證明。
當第一次接觸到這個定理時，我們可以用怎麼樣的角度來看它？以下分成三個層次：
- 第一層次：操作型
- 什麼樣的情況可以使用這個定理？
- 這個定理要如何被正確的使用？
- 第二層次：解釋型
- 如何陳述這個定理？
- 這個定理的重要性是什麼？
- 有這個定理我們可以幹麻？
- 第三層是：內化型
- 這幾個條件背後/幾何上的意義是什麼？
- 當某個條件不滿足的時候，對應回來的high-level概念是什麼造成不是最佳解？
- 可不可以用簡單常見的例子(e.g., basis pursuit)來解釋這個定理？
- 對於舉出的簡單例子，曾經學過的演算法和KKT conditions的關係是如何？
在學校的學習，尤其是工學院和電資學院，常常都只有集中在第一個層次，說難聽點就是會考試就好。但是如果真的是想要做研究的話，後面兩個層次是不能少的。而這些都不是在一時片刻就可以迅速搞定，通常會經過和自己不斷的對話，以及和別人的討論慢慢塑造而成。當你開始習慣用這樣的態度學習每一個你覺得重要的東西時，那麼我就會說你已經在開始慢慢培養你的數學成熟度了。
至於研究的專業度，這邊我想強調的不是研究做得多好或是paper有多少，而是做研究的習慣還有態度。其實這是我一直沒有注意到，是一個幫我寫推薦信的老師跟我聊天時，他特別跟我說我才意識到的。以下用條列的方式舉幾個例子：
- 自己辨識自己寫的東西是否(接近)正確的能力
- 嚴謹清楚地把自己的想法寫下並且和其他人交流溝通
- 對於研究(對學生來說也許是作業)品質的要求
就像那位老師跟我說的，大部分頂尖的人都是很聰明的，所以做研究通常不是在比誰比較聰明，反而比較像是在看個性(也許兩者有很大的正相關？)。而雖然兩個看起來都像是天生的，不過很明顯的後者應該是比較容易後天養成的吧！？所以我也很鼓勵學弟妹(包括勉勵自己)，在求學的過程不斷的培養好的習慣，並且在正確的地方對自己嚴格。
後記
我還蠻晚才下定決心要走理論CS這個領域，在這之前摸索了很多其他不同的領域，雖然也因此讓我覺得起步慢了有點吃虧，不過看過很多東西後，更可以讓我堅信自己喜歡和適合的是什麼。
理論CS在台灣是個還蠻小的領域，也因此相關的資源和資訊蠻不足的。在期待有更多的年輕後輩加入之際，也很歡迎有興趣的人來討論任何相關的問題，我會非常樂意可以幫得上忙！