$
\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 @ UCSD
17 Mar 2017
UC San Diego(UCSD)位於美國西南角靠太平洋和墨西哥的溫暖地區，擁有龐大且diverse的理論CS團隊，和數學系也有緊密的合作關係，雖然學校排名看起來普通，但是據他們所說，這幾年整個學校有往前衝刺的跡象。
參訪流水帳
第一天
San Diego完全是個跟紐約不同的世界，除了天氣之外，景色也很不同，樹木都是綠的，建築物風格也很不同，屋頂大多是磚塊色，然後土黃的身體。而且可以明顯感覺到這邊南美的人很多，像是載我的司機應該就是，他講話我幾乎都要聽第二遍才懂，所以他後來也懶得跟我聊了。
旅館沒有網路上看的奢華，但是也蠻不錯，住的是四人房，和一個北大的共用。東西放一放後我就出去覓食了。繞了一小圈，最後去附近的一個咖啡店，點了起司雞肉三明治還有espresso，都還蠻不錯，三明治有到那個價錢的水準，料很多也很好吃，可惜之後沒有機會，不然還會想再去。
離開咖啡店到集合之前先去海邊繞了一趟，看到可愛的海豹還有很多海鷗，海豹曬太陽還有扭動的樣子真的很療癒，旁邊也有很多小朋友在玩耍，不過好像沒有人敢碰他們就是了。
六點大家從旅館大廳集合出發，發現人意外的很少，後來問一問也才知道UCSD的CS每年Ph.D.生大概就二三十個而已，錄取的大概就是兩到三倍的數量。基本上真強者好像不太會申請UCSD，在Princeton遇到的所有理論CS學生都沒有出現在這裡，聊天時也很少遇到同時有上很前面學校的。
吃飯不小心坐到整桌新生都是中國人，所以整個就比之前在Princeton自在很多，不知道是因為大家都一樣沒那麼超級會聊，還是自己有進步了。因為今天沒有分group坐，所以遇到很多來自不同領域的學長學姊，能夠聽聽不同領域的人的東西也蠻有趣的。
吃完後八點半左右回旅館，然後在大廳和幾個中國人聊天，感想基本上就是覺得姚班真的是怪物訓練機，連北大很厲害的學生也是完全不能比。而且他們都想蠻多的，不見得是自己想做什麼，但是把很多可能性都考慮得很清楚，聊一聊還蠻有趣的。
第二天
UCSD的行程總共有一天半，都是要早上八點在旅館lobby集合然後搭遊覽車去系館吃早餐。今天是邊吃早餐邊聽系所的整體介紹，大致上讓我的感覺是圍繞在這邊曾經有哪些很猛的研究，還有San Diego是個多棒的城市，不過都沒什麼提到理論的研究ＸＤ結束後就開始1-1的行程。這邊的visit讓我覺得比Princeton好的一點是會安排和這邊Ph.D.生一對一的聊天，這實在是個蠻不錯的機會讓我們對學校還有老師有不同角度的了解。
首先先跟一個來自上海交大的Ph.D.生聊，用中文還是爽快多，他就用白板跟我介紹他在做的題目還有方向，可以看得出來他對自己的領域很熟而且也做得很好。基本上他做的是很底層的boolean function analysis，處理一些很根本open的conjecture，像是noise stability還有decision tree深度跟 circuit lower bound之類的關係，算是建立一些重要的數學工具。而他也做得很不錯，第二年就上STOC還是FOCS，現在好像有七篇paper了。聽他說和他老闆Shachar Lovett的互動還蠻不錯的，讓我對UCSD有了很好的第一印象。
後來就跟Shachar Lovett聊天，果然比較有經驗後，現在就比較不會緊張，於是就東扯西聊了一番。主要先聊了一下boolean function analysis這塊，他是說現在基本上大家會的都還是跳脫不出switching lemma的範疇，頂多是一些延伸而已，但是這樣的技術能做到的無法達到optimal，所以大家都在努力找新方向，因此基本上這個方向是蠻重要也很open但是超級難。後來也聊了一下additive combinatorics，對他來說這就是個數學工具幫助我們處理一些不具有代數結構，但是有很類似的東西，特別是關於randomness和structure的關係。不過都是些很high-level的閒聊，所以還是要實際學了才能更深刻的感受吧！這次回台灣後就要好好開始跟課還有看看那些survey papers了。
下一個老師是Mohan Paturi，是這邊比較長老級的，後來聽有些學生說他已經半退休的狀態。感覺他聽到我有Princeton的offer之後就沒有很認真的跟我聊，大概覺得我不會過來吧。跟他聊的內容就比較沒有令我比較印象深刻的東西，我們兩個都很急著要去吃中餐吧。
中午吃還不錯的faculty club，不過聽說平常學校的食物很難吃…
下午又是一連串的1-1行程，和一些學生聊之外還有跟一個ML的老師聊到。這個ML老師雖然知道我一定不會跟她還是很親切地跟我聊很多，然後提到了GAN(Generative Adversarial Network)，好像現在做偏理論一點點的ML人都蠻注意這一塊的。她蠻有意思的把crypto和ML做了連結，說她覺得這兩個領域都像是說給你一些目標然後要去達成，過程中modeling很重要。然後她覺得complexity就比較不是這樣，所以她比較沒有感覺。我算是部分同意部分反對吧，必較complexity很重要的一部分也是在model計算這件事情，只不過可以發展比較完全了一點點，所以很多人可以直接在處理好的定義下做事情吧。
晚上到一個海邊的餐廳，也是在學校裡頭，餐廳有個露天區域，就可以直接看到一望無際的海，很多人衝浪，實在很愜意。後來又跟那個中國學長聊，希望之後如果沒有選這邊也還有機會來拜訪。
第三天
今天也是七點半起床，然後八點check out，九點左右到系館。不知道為什麼早上一直很想睡覺，而且早餐的咖啡很難喝，所以在第一個meeting前又去系館門口買了杯卡布奇諾，結果更難喝⋯
第一個教授是特別從UCB回來和新生meeting的Russell Impagliazzo，是我一開始對UCSD印象最深也最感興趣的教授。之前看一些演講影片對他的印象就是個科學怪人，講話很跳然後有很多不一樣的想法，前一天和學生聊也是聽到他們會把Russell當成oracle來用。結果他遲到了快十分鐘。走路一搖一擺的很可愛，手中拿著一本書和汽水，匆匆忙忙地跟我說抱歉，他還差點找不到辦公室的鑰匙。他的辦公室超亂，到處都是paper還有汽水罐，一屁股坐下來後就直接問我對什麼有興趣，於是就開始亂聊了起來。因為我個人對於他在fine-grained complexity那邊的研究比較沒那麼感興趣，所以主要問他關於derandomization還有circuit lower bound之類的東西，不過他似乎最近做比較少這邊，主要是覺得這塊大家都有點卡住了吧。所以他就提了一些最近和學生在做一個circuit lower bound和learning關係的研究。主要的想法是跟PRG扯上關係，不過他一副不太願意跟我說細節的樣子，大概因為是個ongoing work吧。
下一個教授是Daniele Micciancio，是一個口音有點重但是蠻親切的中年老師，主要的領域是在lattice，光是他念lattice的方式就很有韻味。因為彥霖跟他做得很相關，所以有先和他討論一些可以問的問題，例如說他是怎麼思考high-dimensional的lattice，還有smoothing parameter的發展等等。不過Daniel的回答實在讓我們這些平凡人很吐血，他就說一開始當然會不習慣，但是做久就沒問題了，沒有什麼特別的訣竅…比較有趣的是他說用在lattice的harmonic analysis最當初是數學家寫了一個相關的paper，超短，很難懂，也是隔了一陣子才被CS的人發現拿來用。於是他當初看到有關，就想說學一學，然後就變專家了…後來發現他是Salil在MIT應數的博班同學，難怪把數學都講的跟玩具一樣簡單…不過聊完後也讓我感覺到，基本的數學學習能力也是在博班要學習很重要的一部分，畢竟你不可能在五年把所有該學的數學都學完，甚至之後還要自己發明數學，因此能夠有自我開發學習的能力很重要，需要學習不靠老師和學校也可以自己學起來。
最後meet的一個老師是數學系的Sam Buss，是個和藹可親的老人。好像比較資深的老師對於這種場合都很有自己一套的進行方式，他就先問問我做過什麼對什麼有興趣，然後說說他的，還有介紹一下數學系和理論CS這邊的合作狀況。他基本上是在做proof complexity，是個我真的幾乎不懂的領域，只有之前因為修過model theory所以對於什麼first order logic和incompleteness theorem有ㄧ點概念。Proof complexity這邊主要想要的是從proof system的角度來試圖證明$P\neq NP$。一個最遠大的目標就是證明所有complete且sound的proof system都無法在polynomially many step證明一個NP-complete的問題，例如3-SAT。然而現在人們會做得非常侷限，基本上目前有的separation只有在一種叫做resolution的proof system，想法很簡單，就是把$k$-SAT的clauses們倆倆合併直到不能為止。不用花太多公夫可以證明resolution是complete且sound然後對於$\NP$有個exponential upper bound，而也有人找到一個exponential lower bound for $k$-SAT根據鴿籠原理。不過這樣的結果距離真正有用還差非常遠就是了…
中午是到一家學校裡面的餐廳，在十五樓，原本應該要可以看到海，不過霧太大，所以都看不到。吃飯的時候有另外一個學長跟我講他的研究，也是那個我比較有興趣的教授的學生。他做的主要是additive combinatorics裡面和pseudorandomness有關的研究。基本的問題像是考慮在$\mathbf{GF}(2^n)$中random的集合中會不會有包含夠大的subspace，或是多少的subspace等等。這邊的想法就是說subspace是在$\mathbf{GF}(2^n)$比較有結構的東西，而他們關注的就是在怎樣的random之下可以有足夠可以利用的結構。不過他是沒有跟我講太多實際上的連結，之後回台灣再來好好看那兩篇TCS和additive combinatorics之間關係的survey。
吃完後休息一下後來就有巴士載我們到飛機場，車上和一個印度學生聊，發現他是個猛哥，前面的學校好像只有Princeton沒有(也不知道是不是沒有申請)，最後要去MIT，不過他的領域是系統，跟我很不一樣。兩個人聊天還是比較容易些，所以跟他閒聊了不少，總之我們都覺得還是學習環境和強度以及適合的老師比較重要，而不是這邊很愛強調的天氣吧ＸＤ而他也有提到蠻有趣的一點，他說印度那邊的大學生，有個神秘的習慣就是會大量寄信去找國外的教授一起做研究，像他當初就是這樣跟一個MIT的教授，然後蠻合的來所以之後想要繼續合作。這樣的好壞也許見仁見智，但是感覺上致少是給自己多一些機會。
參訪心得
整體來說的感覺是，UCSD的theory group比Princeton diverse一點，尤其是和數學系的老師(特別是combinatorics和logic)合作密切，而且有個聊得很合說中文的學長還是有差一些。而且透過1-1和學生的聊天，還是可以更瞭解學校還有老師，於是我在第二天晚上就馬上寄信給下一間學校要求要和學生聊天了。這邊不錯的值得跟的老師大概就是Shachar了吧，另外幾個是很適合當作聊天用的，不過其中有個學生跟我偷偷說如果他是我會選Princeton XD。他的理由是覺得Princeton那邊厲害的postdoc比較多，他覺得Ph.D.生可以跟postdoc學到很多東西，是和跟老師學不到的。聽完後覺得蠻有道理的，不過這大概是當其他條件都差不多的時候才要考量的吧。
和Ph.D.生的互動
這次因為和比較多學生聊到，有幾個點讓我特別想要提一下。
- 老師在研究中的定位
我發現在這邊Russell和Mohan他們group的學生有點把老師當成是oracle來用，idea主要都是來自老師們。像是他們舉了個例子說之前有一篇還不錯的結果，就是Russell在group meeting的時候把idea拆成幾個小部分，分配給四個不同的人，然後大家就各自擊破了。這樣看似不錯，但是感覺長遠來看不是太好的事情，畢竟還是要有獨立把研究方向弄出來還有對整體方向掌握的能力。例如我在聊天時問道parallelism在fine-grained complexity裡面的角色目前是如何，那個學長就只有跟我說之前Russel有個東西很類似，但是他講不出個所以然。相較那個中國學長，還有在Princeton遇到的那些，絕大多數都是有和老師一對一合作的經驗，感覺他們對於題目相關的領域整個掌握度就比較高。
*
總結
這次UCSD的visit下來，感受到這邊雖然比較diverse一點，然後厲害的學生還是不少，但是感覺比較沒有主要的方向就是了，整個風格看起來比較隨性。此外這邊真的讓我覺得想跟的老師大概就只有一個(Shachar)，所以跟Princeton比起來還是有段距離。不過這兩間學校下來，實在對於一些大方向的東西有多一些的瞭解認識，也更知道自己有哪些地方需要補強。