$ \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{\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{\R}{\mathbb{R}} \newcommand{\etal} \newcommand{\ie} \newcommand{\eg} \newcommand{\cf} \newcommand{\rank}{\text{rank}} \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{\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]{\lvert #1 \rvert} \newcommand{\Card}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\Norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert} \newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert} \newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert} \newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\Iprod}[1]{\left\langle #1 \right\rangle} \newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle} \newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle} \newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle} \newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace} \newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace} \newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace} \newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace} \newcommand{\bracket}[1]{\lbrack #1 \rbrack} \newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack} \newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack} \newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack} \newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack} \newcommand{\ucorner}[1]{\ulcorner #1 \urcorner} \newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner} \newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner} \newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner} \newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner} \newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil} \newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil} \newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil} \newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor} \newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor} \newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor} \newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor} \newcommand{\lcorner}[1]{\llcorner #1 \lrcorner} \newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner} \newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner} \newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner} \newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner} \newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner} \newcommand{\e}{\varepsilon} \newcommand{\eps}{\varepsilon} \newcommand{\from}{\colon} \newcommand{\super}[2]{#1^{(#2)}} \newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}} \newcommand{\tensor}{\otimes} \newcommand{\eset}{\emptyset} \newcommand{\sse}{\subseteq} \newcommand{\sst}{\substack} \newcommand{\ot}{\otimes} \newcommand{\Esst}[1]{\bbE_{\substack{#1}}} \newcommand{\vbig}{\vphantom{\bigoplus}} \newcommand{\seteq}{\mathrel{\mathop:}=} \newcommand{\defeq}{\stackrel{\mathrm{def}}=} \newcommand{\Mid}{\mathrel{}\middle|\mathrel{}} \newcommand{\Ind}{\mathbf 1} \newcommand{\bits}{\{0,1\}} \newcommand{\sbits}{\{\pm 1\}} \newcommand{\R}{\mathbb R} \newcommand{\Rnn}{\R_{\ge 0}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\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{\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}} \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{\poly}} \newcommand{\polylog}} \newcommand{\loglog}}} \newcommand{\zo}{\{0,1\}} \newcommand{\suchthat} \newcommand{\pr}[1]{\Pr\left[#1\right]} \newcommand{\deffont}{\em} \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}} \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance \newcommand{\xor}{\oplus} \newcommand{\GF}{\mathrm{GF}} \newcommand{\eps}{\varepsilon} \notag $
$ \newcommand{\class}[1]{\mathbf{#1}} \newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements \newcommand{\BPP}{\class{BPP}} \newcommand{\NP}{\class{NP}} \newcommand{\RP}{\class{RP}} \newcommand{\coRP}{\coclass{RP}} \newcommand{\ZPP}{\class{ZPP}} \newcommand{\BQP}{\class{BQP}} \newcommand{\FP}{\class{FP}} \newcommand{\QP}{\class{QuasiP}} \newcommand{\VF}{\class{VF}} \newcommand{\VBP}{\class{VBP}} \newcommand{\VP}{\class{VP}} \newcommand{\VNP}{\class{VNP}} \newcommand{\RNC}{\class{RNC}} \newcommand{\RL}{\class{RL}} \newcommand{\BPL}{\class{BPL}} \newcommand{\coRL}{\coclass{RL}} \newcommand{\IP}{\class{IP}} \newcommand{\AM}{\class{AM}} \newcommand{\MA}{\class{MA}} \newcommand{\SBP}{\class{SBP}} \newcommand{\coAM}{\class{coAM}} \newcommand{\coMA}{\class{coMA}} \renewcommand{\P}{\class{P}} \newcommand\prBPP{\class{prBPP}} \newcommand\prRP{\class{prRP}} \newcommand\prP{\class{prP}} \newcommand{\Ppoly}{\class{P/poly}} \newcommand{\DTIME}{\class{DTIME}} \newcommand{\TIME}{\class{TIME}} \newcommand{\SIZE}{\class{SIZE}} \newcommand{\SPACE}{\class{SPACE}} \newcommand{\ETIME}{\class{E}} \newcommand{\BPTIME}{\class{BPTIME}} \newcommand{\RPTIME}{\class{RPTIME}} \newcommand{\ZPTIME}{\class{ZPTIME}} \newcommand{\EXP}{\class{EXP}} \newcommand{\ZPEXP}{\class{ZPEXP}} \newcommand{\RPEXP}{\class{RPEXP}} \newcommand{\BPEXP}{\class{BPEXP}} \newcommand{\SUBEXP}{\class{SUBEXP}} \newcommand{\NTIME}{\class{NTIME}} \newcommand{\NL}{\class{NL}} \renewcommand{\L}{\class{L}} \newcommand{\NQP}{\class{NQP}} \newcommand{\NEXP}{\class{NEXP}} \newcommand{\coNEXP}{\coclass{NEXP}} \newcommand{\NPSPACE}{\class{NPSPACE}} \newcommand{\PSPACE}{\class{PSPACE}} \newcommand{\NSPACE}{\class{NSPACE}} \newcommand{\coNSPACE}{\coclass{NSPACE}} \newcommand{\coL}{\coclass{L}} \newcommand{\coP}{\coclass{P}} \newcommand{\coNP}{\coclass{NP}} \newcommand{\coNL}{\coclass{NL}} \newcommand{\coNPSPACE}{\coclass{NPSPACE}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\LINSPACE}{\class{LINSPACE}} \newcommand{\qP}{\class{\tilde{P}}} \newcommand{\PH}{\class{PH}} \newcommand{\EXPSPACE}{\class{EXPSPACE}} \newcommand{\SigmaTIME}[1]{\class{\Sigma_{#1}TIME}} \newcommand{\PiTIME}[1]{\class{\Pi_{#1}TIME}} \newcommand{\SigmaP}[1]{\class{\Sigma_{#1}P}} \newcommand{\PiP}[1]{\class{\Pi_{#1}P}} \newcommand{\DeltaP}[1]{\class{\Delta_{#1}P}} \newcommand{\ATIME}{\class{ATIME}} \newcommand{\ASPACE}{\class{ASPACE}} \newcommand{\AP}{\class{AP}} \newcommand{\AL}{\class{AL}} \newcommand{\APSPACE}{\class{APSPACE}} \newcommand{\VNC}[1]{\class{VNC^{#1}}} \newcommand{\NC}[1]{\class{NC^{#1}}} \newcommand{\AC}[1]{\class{AC^{#1}}} \newcommand{\ACC}[1]{\class{ACC^{#1}}} \newcommand{\TC}[1]{\class{TC^{#1}}} \newcommand{\ShP}{\class{\# P}} \newcommand{\PaP}{\class{\oplus P}} \newcommand{\PCP}{\class{PCP}} \newcommand{\kMIP}[1]{\class{#1\mbox{-}MIP}} \newcommand{\MIP}{\class{MIP}} $
$ \newcommand{\textprob}[1]{\text{#1}} \newcommand{\mathprob}[1]{\textbf{#1}} \newcommand{\Satisfiability}{\textprob{Satisfiability}} \newcommand{\SAT}{\textprob{SAT}} \newcommand{\TSAT}{\textprob{3SAT}} \newcommand{\USAT}{\textprob{USAT}} \newcommand{\UNSAT}{\textprob{UNSAT}} \newcommand{\QPSAT}{\textprob{QPSAT}} \newcommand{\TQBF}{\textprob{TQBF}} \newcommand{\LinProg}{\textprob{Linear Programming}} \newcommand{\LP}{\mathprob{LP}} \newcommand{\Factor}{\textprob{Factoring}} \newcommand{\CircVal}{\textprob{Circuit Value}} \newcommand{\CVAL}{\mathprob{CVAL}} \newcommand{\CircSat}{\textprob{Circuit Satisfiability}} \newcommand{\CSAT}{\textprob{CSAT}} \newcommand{\CycleCovers}{\textprob{Cycle Covers}} \newcommand{\MonCircVal}{\textprob{Monotone Circuit Value}} \newcommand{\Reachability}{\textprob{Reachability}} \newcommand{\Unreachability}{\textprob{Unreachability}} \newcommand{\RCH}{\mathprob{RCH}} \newcommand{\BddHalt}{\textprob{Bounded Halting}} \newcommand{\BH}{\mathprob{BH}} \newcommand{\DiscreteLog}{\textprob{Discrete Log}} \newcommand{\REE}{\mathprob{REE}} \newcommand{\QBF}{\mathprob{QBF}} \newcommand{\MCSP}{\mathprob{MCSP}} \newcommand{\GGEO}{\mathprob{GGEO}} \newcommand{\CKTMIN}{\mathprob{CKT-MIN}} \newcommand{\MINCKT}{\mathprob{MIN-CKT}} \newcommand{\IdentityTest}{\textprob{Identity Testing}} \newcommand{\Majority}{\textprob{Majority}} \newcommand{\CountIndSets}{\textprob{\#Independent Sets}} \newcommand{\Parity}{\textprob{Parity}} \newcommand{\Clique}{\textprob{Clique}} \newcommand{\CountCycles}{\textprob{#Cycles}} \newcommand{\CountPerfMatchings}{\textprob{\#Perfect Matchings}} \newcommand{\CountMatchings}{\textprob{\#Matchings}} \newcommand{\CountMatch}{\mathprob{\#Matchings}} \newcommand{\ECSAT}{\mathprob{E#SAT}} \newcommand{\ShSAT}{\mathprob{#SAT}} \newcommand{\ShTSAT}{\mathprob{#3SAT}} \newcommand{\HamCycle}{\textprob{Hamiltonian Cycle}} \newcommand{\Permanent}{\textprob{Permanent}} \newcommand{\ModPermanent}{\textprob{Modular Permanent}} \newcommand{\GraphNoniso}{\textprob{Graph Nonisomorphism}} \newcommand{\GI}{\mathprob{GI}} \newcommand{\GNI}{\mathprob{GNI}} \newcommand{\GraphIso}{\textprob{Graph Isomorphism}} \newcommand{\QuantBoolForm}{\textprob{Quantified Boolean Formulae}} \newcommand{\GenGeography}{\textprob{Generalized Geography}} \newcommand{\MAXTSAT}{\mathprob{Max3SAT}} \newcommand{\GapMaxTSAT}{\mathprob{GapMax3SAT}} \newcommand{\ELIN}{\mathprob{E3LIN2}} \newcommand{\CSP}{\mathprob{CSP}} \newcommand{\Lin}{\mathprob{Lin}} \newcommand{\ONE}{\mathbf{ONE}} \newcommand{\ZERO}{\mathbf{ZERO}} \newcommand{\yes} \newcommand{\no} $
$ \newcommand{\undefined}{} \newcommand{\hfill}{} \newcommand{\qedhere}{\square} \newcommand{\qed}{\square} \newcommand{\ensuremath}[1]{#1} \newcommand{\bit}{\{0,1\}} \newcommand{\Bit}{\{-1,1\}} \newcommand{\Stab}{\mathbf{Stab}} \newcommand{\NS}{\mathbf{NS}} \newcommand{\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{\R}{\mathbb{R}} \newcommand{\etal} \newcommand{\ie} \newcommand{\eg} \newcommand{\cf} \newcommand{\rank}{\text{rank}} \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{\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]{\lvert #1 \rvert} \newcommand{\Card}[1]{\left\lvert #1 \right\rvert} \newcommand{\bigcard}[1]{\bigl\lvert #1 \bigr\rvert} \newcommand{\Bigcard}[1]{\Bigl\lvert #1 \Bigr\rvert} \newcommand{\biggcard}[1]{\biggl\lvert #1 \biggr\rvert} \newcommand{\Biggcard}[1]{\Biggl\lvert #1 \Biggr\rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\Norm}[1]{\left\lVert #1 \right\rVert} \newcommand{\bignorm}[1]{\bigl\lVert #1 \bigr\rVert} \newcommand{\Bignorm}[1]{\Bigl\lVert #1 \Bigr\rVert} \newcommand{\biggnorm}[1]{\biggl\lVert #1 \biggr\rVert} \newcommand{\Biggnorm}[1]{\Biggl\lVert #1 \Biggr\rVert} \newcommand{\iprod}[1]{\langle #1 \rangle} \newcommand{\Iprod}[1]{\left\langle #1 \right\rangle} \newcommand{\bigiprod}[1]{\bigl\langle #1 \bigr\rangle} \newcommand{\Bigiprod}[1]{\Bigl\langle #1 \Bigr\rangle} \newcommand{\biggiprod}[1]{\biggl\langle #1 \biggr\rangle} \newcommand{\Biggiprod}[1]{\Biggl\langle #1 \Biggr\rangle} \newcommand{\set}[1]{\lbrace #1 \rbrace} \newcommand{\Set}[1]{\left\lbrace #1 \right\rbrace} \newcommand{\bigset}[1]{\bigl\lbrace #1 \bigr\rbrace} \newcommand{\Bigset}[1]{\Bigl\lbrace #1 \Bigr\rbrace} \newcommand{\biggset}[1]{\biggl\lbrace #1 \biggr\rbrace} \newcommand{\Biggset}[1]{\Biggl\lbrace #1 \Biggr\rbrace} \newcommand{\bracket}[1]{\lbrack #1 \rbrack} \newcommand{\Bracket}[1]{\left\lbrack #1 \right\rbrack} \newcommand{\bigbracket}[1]{\bigl\lbrack #1 \bigr\rbrack} \newcommand{\Bigbracket}[1]{\Bigl\lbrack #1 \Bigr\rbrack} \newcommand{\biggbracket}[1]{\biggl\lbrack #1 \biggr\rbrack} \newcommand{\Biggbracket}[1]{\Biggl\lbrack #1 \Biggr\rbrack} \newcommand{\ucorner}[1]{\ulcorner #1 \urcorner} \newcommand{\Ucorner}[1]{\left\ulcorner #1 \right\urcorner} \newcommand{\bigucorner}[1]{\bigl\ulcorner #1 \bigr\urcorner} \newcommand{\Bigucorner}[1]{\Bigl\ulcorner #1 \Bigr\urcorner} \newcommand{\biggucorner}[1]{\biggl\ulcorner #1 \biggr\urcorner} \newcommand{\Biggucorner}[1]{\Biggl\ulcorner #1 \Biggr\urcorner} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\Ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\bigceil}[1]{\bigl\lceil #1 \bigr\rceil} \newcommand{\Bigceil}[1]{\Bigl\lceil #1 \Bigr\rceil} \newcommand{\biggceil}[1]{\biggl\lceil #1 \biggr\rceil} \newcommand{\Biggceil}[1]{\Biggl\lceil #1 \Biggr\rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\Floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\bigfloor}[1]{\bigl\lfloor #1 \bigr\rfloor} \newcommand{\Bigfloor}[1]{\Bigl\lfloor #1 \Bigr\rfloor} \newcommand{\biggfloor}[1]{\biggl\lfloor #1 \biggr\rfloor} \newcommand{\Biggfloor}[1]{\Biggl\lfloor #1 \Biggr\rfloor} \newcommand{\lcorner}[1]{\llcorner #1 \lrcorner} \newcommand{\Lcorner}[1]{\left\llcorner #1 \right\lrcorner} \newcommand{\biglcorner}[1]{\bigl\llcorner #1 \bigr\lrcorner} \newcommand{\Biglcorner}[1]{\Bigl\llcorner #1 \Bigr\lrcorner} \newcommand{\bigglcorner}[1]{\biggl\llcorner #1 \biggr\lrcorner} \newcommand{\Bigglcorner}[1]{\Biggl\llcorner #1 \Biggr\lrcorner} \newcommand{\e}{\varepsilon} \newcommand{\eps}{\varepsilon} \newcommand{\from}{\colon} \newcommand{\super}[2]{#1^{(#2)}} \newcommand{\varsuper}[2]{#1^{\scriptscriptstyle (#2)}} \newcommand{\tensor}{\otimes} \newcommand{\eset}{\emptyset} \newcommand{\sse}{\subseteq} \newcommand{\sst}{\substack} \newcommand{\ot}{\otimes} \newcommand{\Esst}[1]{\bbE_{\substack{#1}}} \newcommand{\vbig}{\vphantom{\bigoplus}} \newcommand{\seteq}{\mathrel{\mathop:}=} \newcommand{\defeq}{\stackrel{\mathrm{def}}=} \newcommand{\Mid}{\mathrel{}\middle|\mathrel{}} \newcommand{\Ind}{\mathbf 1} \newcommand{\bits}{\{0,1\}} \newcommand{\sbits}{\{\pm 1\}} \newcommand{\R}{\mathbb R} \newcommand{\Rnn}{\R_{\ge 0}} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\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{\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}} \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{\poly}} \newcommand{\polylog}} \newcommand{\loglog}}} \newcommand{\zo}{\{0,1\}} \newcommand{\suchthat} \newcommand{\pr}[1]{\Pr\left[#1\right]} \newcommand{\deffont}{\em} \newcommand{\getsr}{\mathbin{\stackrel{\mbox{\tiny R}}{\gets}}} \newcommand{\Exp}{\mathop{\mathrm E}\displaylimits} % expectation \newcommand{\Var}{\mathop{\mathrm Var}\displaylimits} % variance \newcommand{\xor}{\oplus} \newcommand{\GF}{\mathrm{GF}} \newcommand{\eps}{\varepsilon} \notag $
$ \newcommand{\class}[1]{\mathbf{#1}} \newcommand{\coclass}[1]{\mathbf{co\mbox{-}#1}} % and their complements \newcommand{\BPP}{\class{BPP}} \newcommand{\NP}{\class{NP}} \newcommand{\RP}{\class{RP}} \newcommand{\coRP}{\coclass{RP}} \newcommand{\ZPP}{\class{ZPP}} \newcommand{\BQP}{\class{BQP}} \newcommand{\FP}{\class{FP}} \newcommand{\QP}{\class{QuasiP}} \newcommand{\VF}{\class{VF}} \newcommand{\VBP}{\class{VBP}} \newcommand{\VP}{\class{VP}} \newcommand{\VNP}{\class{VNP}} \newcommand{\RNC}{\class{RNC}} \newcommand{\RL}{\class{RL}} \newcommand{\BPL}{\class{BPL}} \newcommand{\coRL}{\coclass{RL}} \newcommand{\IP}{\class{IP}} \newcommand{\AM}{\class{AM}} \newcommand{\MA}{\class{MA}} \newcommand{\SBP}{\class{SBP}} \newcommand{\coAM}{\class{coAM}} \newcommand{\coMA}{\class{coMA}} \renewcommand{\P}{\class{P}} \newcommand\prBPP{\class{prBPP}} \newcommand\prRP{\class{prRP}} \newcommand\prP{\class{prP}} \newcommand{\Ppoly}{\class{P/poly}} \newcommand{\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} $

CCC 2018

Few weeks ago, I attended the 33rd Computational Complexity Conference (CCC 2018) at UCSD. It was my first time going to CCC and I really enjoyed it a lot. As some of my friends told me before, since CCC is quite small and focused (in complexity), sometimes one can find it more useful and helpful. Personally I even like CCC 2018 more than FOCS 2017. The following are some papers that I found interesting to me during the conference. I decided to carefully study these papers and write some thoughts about them after the conference, however, it took much more time than I expected to finish this task.

The Power of Natural Properties as Oracles

Author(s): Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich.

The goal of this paper is two-fold. Firstly they want to investigate how powerful a natural property is following the learning with natural proof work by (Carmosino, Impagliazzo, Kabanets, & Kolokolova, 2016). On the other hand, they provide envidence that the minimum circuit size problem, i.e., $\MCSP$, is as hard as $\NP$.

Here, we list some of their results in the following.

  • $\ZPEXP^{\MCSP}\not\subseteq\Ppoly$ improving the previous $\ZPEXP^{\NP}\not\subseteq\Ppoly$.
  • $\ZPP^{\MCSP}/1\not\subseteq\SIZE[n^k]$ for all $k\in\N$.
  • Suppose indistinguishable ofuscation exists, then $\MCSP\in\ZPP$ if and only if $\NP=\ZPP$.
  • Replace the $\NP$ oracle in many complexity relations with $\MCSP$ oracle.

Collapse theorem

Let $\Gamma\in\{\PaP,\ShP,\PSPACE,\EXP,\NEXP,\EXP^{\NP}\}$. If $\Gamma\subseteq\Ppoly$, then $\Gamma\subseteq\ZPP^{\MCSP}$.

To interpret this theorem, one have to compare with the previous results. Prior to this work, $\Gamma$ would only collapses to $\MA$ (see this note) which lies in $\ZPP^{\NP}$. The above theorem in some sense indicates the power of $\MCSP$ being an oracle is as powerful as $\SAT$.

Circuit lower bounds

$\ZPP^{\MCSP}/1\not\subseteq\SIZE[n^k]$ for all $k\in\N$.

Note that this is an analogy to the $\MA/1\not\subseteq\SIZE[n^k]$ due to Santhanam (Santhanam, 2009) (see this note). As we mentioned previously, $\MA\subseteq\ZPP^{\NP}$ and thus $\ZPP^{\MCSP}$ can be thought of as a $\MCSP$ analogy for $\MA$.

Key technique

The following is a kel lemma extracted from (Carmosino, Impagliazzo, Kabanets, & Kolokolova, 2016) using natural proof (see this note) to learn boolean function.

Let $\mathcal{R}$ be a strongly useful natural proof and let $L$ be a downward self-reducible and self-correctable language. Then, there exists a randomized algorithm with oracle queries to $\mathcal{R}$ such that on input $x$, output $L(x)$ correctly with probability at least $1-1/\poly(n)$ in time $\poly(\card{x},\text{size}(L))$.

An immediate corollary would be a conditional collapse of $\PSPACE$ to $\BPP^{\MCSP}$ since there is a downward self-reducible and self-correctable language in $\PSPACE$ and $\MCSP$ is a strongly useful natural proof.

To move from $\BPP^{\MCSP}$ to $\ZPP^{\MCSP}$, we need one more lemma as follows.

Let $\mathcal{R}$ be a strongly useful natural property. Then, $\BPP\subseteq\ZPP^{\mathcal{R}}$. Moreover, if $\mathcal{R}\in\Ppoly$, then $\BPP^{\mathcal{R}}=\ZPP^{\mathcal{R}}$.

Some thoughts

To some extent, the techniques used in this paper are not that surprising after the CIKK paper, however, the high-level message is informative. I feel that these results all highly rely on the self-reducibility of a $\PSPACE$-complete language. Is that possible to go beyond this? Say having similar results for lower complexity classes that do not have a self-reducible language?

Pseudorandom Generators from Polarizing Random Walks

Author(s): Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett.

This work gives a new framework of constructing pseudo random generator (PRG) by using fractional PRG. They construct PRG for functions with low sensitivity with better seed length as well as PRGs for other family of well-studied functions. The key constrution is a fractional PRG for function with exponentially decaying $\ell_1$ tail. In the following, we will first define some notations and present some of their results.

Here, we think of PRG as a random variable $X$ distributes in ${-1,1}^n$ defined as $X=G(U_r)$ where $G:{-1,1}^r\rightarrow{-1,1}^n$ is the generator function, $U_r$ is uniformly distributed over ${-1,1}^r$, and $r$ is the seed length. We say $X$ $\epsilon$-fools a function $f:{-1,1}^n\rightarrow{-1,1}$ if \begin{equation} \left|\E[f(X)]-\E[f(U_n)]\right|\leq\epsilon. \end{equation} The goal is to minimize the seed length $r$. Note that there are other ways to define PRG and they are basically equivalent.

Fractional PRG

A fractional PRG prosed in this paper is a random variable $X$ distributes in $[-1,1]^n$ instead of ${-1,1}^n$ while having the same $\epsilon$-fool property. However, to avoid triviality ($X$ always being $0^n$), we say $X$ is $p$-noticeable for some $p>0$ if $\E[X^2]\geq p^2$.

The paper mentions that a $p$-noticeable fractional PRG that fools function with exponentially decaying $\ell_1$ Fourier tail can be constructed with bounded-wise independent random variables. Concretely, they have the following lemma.

For any $a,b>0$ define $\mathcal{F}_{a,b}^n=\{f\ |\ \sum_{S\subseteq[n]:|S|=k}\card{\hat{f}(S)}\leq a\cdot b^k\}$ be the family of functions with exponentially decaying $\ell_1$ Fourier tail. There exists a $p$-noticeable fractional PRG $X$ that $\epsilon$-fools $\mathcal{F}_{a,b}^n$ with seed length $O(\log\log n+\log(a/\epsilon))$ and $p=\frac{1}{4b^2}$.

Note that many well-studied family of boolean functions have exponentially decaying $\ell_1$ Fourier tail. For instance, $\AC{0}$ circuit, functions with bounded sensitivity, functions computed by certain branching programs, etc.

From fractional PRG to PRG

Now that we have fractional PRG for a bunch of boolean function families, the goal is to construct PRG for them. This paper shows how to use fractional PRG to construct PRG for the same family of functions with little blow-up in seed length.

The key idea is using a sequence of indpendent fractional PRG to do a random walk in $[-1,1]^n$ and then rounding to boolean value after few steps. The analysis is based on polarization in one-dimensional martingale. Here, we skip the proof and only state the theorem as follows. Note that we need the function family $\mathcal{F}$ to have some self-trstrictable property in the sense that after fixing some input, the function still lies in the same family.

Let $X_1,X_2,\dots,X_t$ be independent $p$-noticeable fractional PRG that $\epsilon$-fools self-restrictable $\mathcal{F}_{a,b}^n$. When $t=O(\log(n/\epsilon)/p)$, we have $X=M(X_1,X_2,\dots,X_t)$ a PRG that $(t+1)\epsilon$-fools $\mathcal{F}_{a,b}^n$ where $M(\cdot,\dots,\cdot)$ is some random walk function.

Some thoughts

The idea of fractional PRG is quite interesting and it is surprising to me that one can really use it to contruct PRG with seed lengths comparable to other highly non-trivial PRG for various computational models. Also, the recent exiciting oracle separation for $\BQP$ and $\PH$ used the analysis in this paper. I still haven’t fully understood the intuition why their tools overcome the previous barrier and it would be interesting to see if this can be applied in other places.

Another intersting research direction here could be generalizing the idea of fractional PRG as the authors suggested in the end the talk/paper. Basically, the currect reduction from fractional PRG to PRG is via a simple summation and rounding. Could a more complicated composition of fractional PRG be more efficient?

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits

Author(s): Shuichi Hirahara, Igor C. Oliveira, and Rahul Santhanam.

The minimum circuit size problem (MCSP) is a well-known problem in $\NP$ in the situation that people do not know if MCSP lies in $\P$ or is $\NP$-complete. The input of MCSP is the truth table of a boolean function $f$ and an integer $s$ such that the goal is to decide whether there exists a circuit of size at most $s$ computing $f$. Currently there’s no evidence against the $\NP$-hardness of MCSP. The only obstacle in showing MCSP is $\NP$-hard is due to Kabanets and Cai showing that a natural reduction from SAT to MCSP would imply a super-polynomial lower bound against $\mathbf{E}$, the family of problems solvable in linear exponential time.

There are not so many results either even one considers MCSP for restricted circuit family. In 1979, Masek showed DNF-MCSP is $\NP$-hard and this is the state-of-the-art. This paper gives the first improvement for the hardness of MCSP for depth-3 circuit.

Theorem The MCSP for $\text{Or}\circ\text{And}\circ\text{Mod}_m$ is $\NP$-hard.

The main idea is viewing the $\text{Or}\circ\text{And}\circ\text{Mod}_m$ as an indicator function for an union of affine spaces. Concretely, let’s start with $m=2$ where $\text{Mod}_2$ is the parity gate. One can see that the preimage of 1 of each parity gate gives an affine space. As a result, one can think of a $\text{Or}\circ\text{And}\circ\text{Mod}_m$ circuit for boolean function $f$ as using affine spaces to cover the 1-preimage of $f$. Quantitatively, the number of affine spaces needed is a lower bound for the number of $\text{And}$ gates needed.

A story of AM and UNIQUE-SAT

Author(s): Ilya Volkovich.

This paper was presented by Ilya in the rump session. He showed that $\AM=\SBP$ if Unique-Sat ($\USAT$) is $\NP$-hard. Recall that $\MA\subseteq\SBP\subseteq\AM$ and whether $\MA$ euqals to $\AM$ is one of the important question in complexity theory. This paper can be thought of as an indication of $\MA=\AM$. A natural open question after this work would be either (i) improving the assumption, i.e., basing on more believing condition than the $\NP$-hardness of $\USAT$, or (ii) improving the conclusion, i.e., $\MA=\AM$ instead of $\AM=\SBP$.

Let us start with some definitions.

$\MA$, $\SBP$, and $\AM$

One convenient way to view $\MA$ is to think of it as $\NP$ with a randomized verifier. Formally, a language $L$ is in $\MA$ if there exists a polynomial-time computable predicate $R(x,w,r)$ such that \begin{align*} x\in L\Rightarrow\ \exists w,\ \Pr_r[R(x,w,r)=1]\geq\frac{2}{3},\\ x\not\in L\Rightarrow\ \forall w,\ \Pr_r[R(x,w,r)=1]\leq\frac{1}{3}. \end{align*}

As for $\AM$, the verifier (Arthur) will toss the randomness before the prover (Merlin) sends the witness. It immediately follows from the definitions that $\MA\subseteq\AM$. Intuitively, one can think of $\AM$ as a class of languages that have a randomized reduction to $\NP$. Formally, we say $L\in\AM$ if there exists a polynomial-time computable predicate $R(x,w,r)$ such that \begin{align*} x\in L\Rightarrow\ \Pr_r[\exists w,\ R(x,w,r)=1]\geq\frac{2}{3},\\ x\not\in L\Rightarrow\ \Pr_r[\exists w,\ R(x,w,r)=1]\leq\frac{1}{3}. \end{align*}

$\SBP$ is not as well known as $\MA$ and $\AM$ since most complexity courses would not introduce it. However, it is a fairly natural existence between these two very important complexity classes. Let us directly state the definition of $\SBP$. We say $L\in\SBP$ if there exists a polynomial-time computable predicate $R(x,r)$ such that there exists $\epsilon>0$ and $k\in\N$, \begin{align*} x\in L\Rightarrow\ \Pr_r[R(x,r)=1]\geq(1+\epsilon)\cdot\frac{1}{2^{n^k}},\\ x\not\in L\Rightarrow\ \Pr_r[R(x,r)=1]\leq(1-\epsilon)\cdot\frac{1}{2^{n^k}}. \end{align*} It is a simple exercise to check $\MA\subseteq\SBP\subseteq\AM$ by viewing the witness $w$ in $\MA$ and $\AM$ as a part of the randomness $r$.

Intuition for the conditional collapse theorem

We are going to briefly explain the intuition for the following main theorem.

If $\USAT$ is $\NP$-hard, then $\AM=\SBP$.

The idea is actualy quite straightforward. Recall the definition of $\AM$. Suppose for a language $L\in\AM$, each yes instance $x\in L$ has a unique witness $w$. Then it immediately follows from the definition that $L\in\SBP$ by simply let the randomness to be $r’=(w,r)$. Namely, to collapse $\AM$ into $\SBP$, it suffices to transform every language $L\in\AM$ to a language that has unique witness.

With this sufficient condition in mind, it is then no difficult to see that under the assumption that $\USAT$ is $\NP$-hard, one can collapse $\AM$ into $\SBP$.

Some thoughts

This is quite a cute paper that gives a detailed connection between $\MA,\SBP,\AM$. Though the conditional collapse theorem is not too deep after knowing the definitions of these classes, the paper points out a pave to prove $\AM\subseteq\MA$. A the paper suggested in the end, some natural open questions would then be either improving the assumption or improving the consequence. I personally would be more interested in finding more suitable assumption to collapse $\AM$.

References

  1. Carmosino, M. L., Impagliazzo, R., Kabanets, V., & Kolokolova, A. (2016). Learning algorithms from natural proofs. In LIPIcs-Leibniz International Proceedings in Informatics (Vol. 50). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

    Ph.D. 第一年心得

    其實2018 Spring的學期已經結束一個月左右了,也即將要從台灣回去波士頓。來到了一個新的環境求學,在自己不斷繼續成長的同時,要適應新的研究模式、身邊的合作對象、修課方式,甚至是語言還有表達與溝通。一直想要找個機會整理一下這段時間下來的想法,很多不同的思緒混在一起,讓我就這樣不知不覺拖到現在,終於下定決心就不管太多寫就對了。

    Read more...

    Novermber, 2017

    一轉眼已經來到劍橋三個半月了,Ph.D.的第一個學期也即將邁入尾聲,隨著衣服越穿越多,似乎也開始漸漸抓到生活還有做研究的步調。在如此耗腦力的環境之下,了解自己在什麼時候該做什麼事情決定了做事效率,一旦盲目地工作,很有可能最後仍然是一場空。

    現在的生活主要圍繞在三個大方向上面:研究、學習、休息。研究是個需要高度集中力,以及讓思緒自由奔馳的狀態,因此除了需要精神好之外,也很需要一個放鬆自在的環境。也因此當我在想研究的時候,很喜歡四處的移動,通常是從房間開始,播一些輕鬆的音樂,然後好好整理一下之前想過的方向,然後試圖找些可以突破的點,一旦在一個方向卡住一段時間後,就會慢慢的移動到辦公室,或是找個喜歡的咖啡店(尤其是最近愛上了熱巧克力店L.A. Burdick)。最重要的是要邊走邊寫,時常一些盲點都是在邊走邊想的時候釐清的,然後一到下個地方後,就可以把之前卡住的地方寫清楚,然後往下一個方向前進。

    除了研究之外,持續不斷的學習也是身為一個Ph.D.學生(甚至是in general的學術工作者)不可以忽視的一件事情。這學期雖然修了兩門課,但是如果只有把修課該做的事情做完其實是很不夠的。尤其是這邊修課的感覺(至少以理論CS來說)是非常地強調自主性的,老師不會去管你的出席或是預習複習狀況,作業量也沒有想像中的大,不一定需要把上課教的東西完全搞懂還是可以把作業寫出來。這樣的好處是可以讓學生自由的選擇自己有興趣的方向好好的深入學習,而壞處就是學生真的必須要去認真思考自己想要在這門課獲得什麼,不然很容易一下子時間就過去了,然後發現自己什麼也沒有學到。而在課堂之外,學習深度與廣度的增強也是需要依靠每天一點一滴的累積的。看看身邊的senior Ph.D. students,總覺得他們懂的東西好多,不見得是跟他們修過的課或是做過的研究相關,能夠做到這樣的關鍵就是持續一點一滴學習的累積。這有可能是透過聽演講獲得的,也有可能是靠讀paper還有看書學到的。不管是哪種方法,在課堂還有研究之外的學習才是一個人的內功,決定了他可以走得多遠。在體會到這個觀念之後,我開始慢慢規劃讓自己有個固定可以看書或是看paper的時間,目前終於發現在每天的一大早是個很好的時機。也就是在七點多起床到八點多吃飯之間的這一小時,讀一些平常很想看的書(例如代數幾何)還有paper。通常這個時間是個腦袋還沒有很靈活,但是可以正常運作的時間,拿來學習可是最剛好不過的了。

    在研究還有認真學習之外,生活的平衡也是維持健康的身心不可或缺的一部份。這學期做了大量的課外活動,試圖在研究學習還有生活之中找到平衡。有時候覺得自己相較於同學朋友之下有點太混了,不過說實在跟剛開學時很拼的時期比起來,我感覺做事的效率還有成果沒有差太多。”適當”的放鬆對我來說的確可以讓我在該認真的時候更能夠專注,把事情有效率地做好,同時也更享受在劍橋舒服的生活。

    雨後讀不下書的夜晚

    連續下了幾天雨的劍橋,就跟梅雨季的台北差不多令人鬱悶,開學的第三週,齒輪漸漸進入了軌道。五年的Ph.D.看起來很長,但是看看身邊的學長學姊們,似乎看見了一年後、兩年後、三年後的自己,不久後也要站到他們的位子上了。

    讀書和學習最大的壓力始終是來自自己,第一個月還沒過完已經開始有點胃痛了,也不知道是因為最近太常自己做菜為,衛生沒有做好。還是給自己的目標訂太高,太在意和別人的差距,太急著想要有點明顯的進步。明明知道不要給自己太多壓力,五年慢慢的來,享受這一切過程,但是每當和別人討論時無法清楚地理解,沒辦法提出好的問題,都還是會很不甘心,覺得自己要更好。

    看來還是不懂得接受失敗吧!

    上海特訓班

    去年上海財經大學成立了理論計算機科學研究中心,由陸品燕老師領導,目前已經有五位全職的老師/研究員,再加上每年暑假期間絡繹不絕的訪客,這裡儼然成了東方理論計算機的新星。

    去年暑假我就和鐘老師來這邊拜訪了兩個禮拜,事隔一年,在將要去美國攻讀Ph.D.之際,再次重遊。雖然和這邊的學生老師交流沒有預期的多,但是和同行的鍾豪還有鐘老師將近兩週來的密切相處,還是讓我在研究還有思想體系上有了些成長。

    Read more...

    與Bell's inequality的約會

    這週末趁著去上海前的空擋,到台南四天三夜拜訪親朋好友,七月底去唸博士班之後,見面將變得不這麼容易了,雖然這幾年縱使在台灣也是聚少離多就是了。

    阿霈是我在高中時的摯友,我們倆當時都熱愛物理,雖然喜歡的方面可能不太一樣(我比較偏向喜歡物理中數學的漂亮)。還記得那時候阿霈就是個對理解東西很固執的人,在台灣高中教育的氛圍下,大部分人講求用最快速的方式把知識記起來考高分,但是阿霈總是會很鑽牛角尖的想要徹底理解清楚。當時還覺得他有點奇怪,現在反倒是很羨慕他很早就有著批判學習的精神。

    Read more...

    寫於柯潔戰敗後

    如同眾人意料中一般,20年前深藍(Deep Blue)擊敗人類西洋棋王Garry Kasparov,這一天,AlphaGo擊敗了人類圍棋第一的柯潔。從兒時的故事,到親眼隔著螢幕看到淚灑黑白之間,心中雖然不意外,但仍然震驚於這一天如此快的到來。

    從小的時候就受爸媽影響開始學圍棋,雖然自己下不出來,但是看到高手過招,還是能夠欣賞每一步的奧妙(這也是$\P\neq\NP$的一個例證吧!?)。還記得約莫在升上國中左右的時期,電腦圍棋開始漸漸普及,在家連個網路就可以和來自世界(其實也就只是中日台韓)的網際對弈,也因此越來越不去棋院了。有時候一時之間在網路上沒有配對到對手,又棋癮發作,就會點開電腦自動下棋模式,然後狠狠的把電爆對手。還記得國中的我可以讓當時網路上最厲害的程式兩三子,仍然輕鬆獲勝。

    Read more...

    5/14 - 5/21, 2017

    最近的學習是在五花八門的混亂,還有鑽牛角尖的細節中來回交替。因為下定決心想要在九月開學前好好把一些基礎學好,於是列了一大票學習清單。一兩個月下來,每個好像都讀了一些,細節也學到了不少,但是又好像都沒有把整個經脈打通,這感覺有點像一個棒球選手把內野、外野、投手、捕手的基礎的摸一遍了,但是還是沒有能力上場打球。每天看著精彩的球賽不斷上演,卻只能在板凳繼續打轉。

    Read more...

    鴻門宴

    今晚有一頓免費的日式料理大餐,滿心期待的踏入捷運,坐在位子上聽著熟悉的貝多芬第四號鋼琴奏鳴曲,大小聲精細的轉變依然令人不自覺搖擺身體。忽然一陣念頭襲來:為什麼這麼突然要請客呢?該不會是場鴻門宴吧!?

    Read more...

    等效不等式 (Isoperimetric Inequality)

    \begin{equation} \int_{\mathbb{R}^n}\card{u}^{\frac{n}{n-1}}\leq n^{-1}\omega_n^{-1/n}\int_{\mathbb{R}^n}\card{\nabla u}. \end{equation}

      球
      在歐式空間中
     如同他圓滾的外觀
    竭盡所能的向外擴張
     用力嘲笑正立方體
      不懂利用有限的
      空間

    \begin{equation} \gamma_s(\partial A)\geq\phi\circ\Phi^{-1}(\gamma(A)). \end{equation}

     在 高 斯 世 界
     半 空 間 是 座
     無 止 境 高 牆
     任 何 戳 打 槌
     仍 矗 立 挺 拔

    2017 Ph.D. 申請心得

    從大三開始漸漸有了想要出國留學念博士的想法,經過一兩年在各個實驗室還有不同領域的歷練後,在大四的寒假下定決心要申請theoretical CS (TCS)相關的博士,並且目標鎖定在Harvard。從去年(2016)九月開始,與幾個同屆要申請的好友,還有許多學長、老師、家人的幫助之下,終於完成申請,並且熬過了痛苦的等待放榜的冬天,最終要如願在今年(2017)秋天到Harvard念博士囉!

    Read more...

    Visit Day @ Harvard University

    Harvard基本上是我一直以來的top choice,首先收我的Boaz Barak是我最想跟的教授,然後這邊也還有另外幾個我感興趣的老師像是Madu SudanSalil Vadhan,加上離MIT很近,可以和那邊互動也是一個大加分。在visit day之前,我的想法是如果Harvard沒有讓我覺得有扣分的地方的話,那就是會選Harvard了。

    Read more...

    Visit Day @ UT Austin

    UC Austin是這次參訪的四間學校中最炎熱的一間,幾乎跟台灣有得比。這邊理論CS的老師總共有九位,而且各自做的領域蠻diverse,其中Dana Moshkovitz是我最有興趣也是當初最先聯絡我的老師,而且她的老公Scott Aaronson更是理論CS界的奇葩,是個什麼都做什麼都厲害的人,因此就老師層面而言,UT Austin和Harvard是我主要考慮的兩間。

    Read more...

    Visit Day @ UCSD

    UC San Diego(UCSD)位於美國西南角靠太平洋和墨西哥的溫暖地區,擁有龐大且diverse的理論CS團隊,和數學系也有緊密的合作關係,雖然學校排名看起來普通,但是據他們所說,這幾年整個學校有往前衝刺的跡象。

    Read more...

    Visit Day @ Princeton University

    Princeton是理論CS特別是complexity theory的傳統強校,而且離高等研究院(IAS)距離十分鐘的車程,再加上位於兩座大城:紐約和費城中間的優雅寧靜區域,是個適合做理論研究地方。

    Read more...

    搬家

    搬家了,是有記憶以來第四次搬家,雖然這個家是住最短的一個,但是實際參與了搬家的過程,卻反而感觸特別深刻。

    Read more...

    Test Math

    This post aims to test the math environment on this website.

    Read more...

    主動學習者計畫 - 期末心得

    隨著梅雨季的到來,為期八個月的主動者學習計畫也將要劃下句點,規劃了三個多月的期末專文及心得總結:《探索計算的極限》也終於如期完成,看著這些一點一滴累積下來的成果,心中實在是既感動又興奮。

    Read more...

    第二十二週回顧

    最近自主學習的進度來到了隨機抽出器(Randomness extractor),實在非常的神秘,在這邊簡單記錄一下目前看完的心得。

    Read more...

    第二十一週回顧

    最近除了正常的讀書做研究之外,大部分的時間都花在寫文章上面,而在數次的閱稿餐會中,讓來自不同背景的朋友看看我寫的文章,才發現原本我覺得很平易近人的內容,其實大家的感受都差很多。最明顯的例子就是介紹一個新觀念的方法,我在介紹一個新的東西時,會很習慣從比較高觀點,或是抽象的角度做宏觀的解釋。有時候自己掌握的不太好,就會變得有些虛無縹緲,讓人抓不到重點,在幾篇設定為大方向介紹的文章中就很明顯地出現這種情況。於是這時候幫我試讀的朋友就會很痛苦,紛紛向我抱怨沒辦法抓到我想要表達的重點,看過去覺得講的內容頭頭是道,但是看完後卻覺得沒有實際接受到什麼內容。

    Read more...

    第二十週回顧

    雖然最近被研究還有寫文章佔據了大部分的時間,不過靠著番茄工作法(Pomodoro Technique)的幫助,讓我可以在很大塊的忙碌時間中,抽取出小塊小塊的零碎時間,來完成其他的事情。這對於自主學習計畫的進度,或是修課的複習、功課等等,都有看起來雖小,但是重要的關鍵影響。

    Read more...

    第十九週回顧

    這禮拜開始嘗試用一個電腦的App(Pomodone)來監測我的時間分配,然後發現的確出現不少的問題。首先是時間分配非常不均勻,我花了超過三分之一的時間在圖論上面,因為這門課每個禮拜都有五到六題的作業,而且最近的題目困難到連我要把解答看懂都要花很久的時間(因為大部分的題目都是十幾年前人家的一篇論文…)。於是這樣弄下來,我平均一個禮拜不算上課大概都還花了十五個小時在上面。

    Read more...

    第十八週回顧

    這是一個非常飽滿的禮拜,禮拜一大部分的時間都在處理研究還有跟老師討論,禮拜二則是花了一半的時間準備讀書會要報告的講義,禮拜三則是從早到晚滿滿的行程,禮拜四下午進行了這學期第一個期中考,一直到了禮拜五才終於有喘息的空間。

    Read more...

    第十七週回顧

    這禮拜是個忙亂的一週,兩個作業的死線把讀書的計畫稍微打亂了。再加上週末回台中看棒球校隊打大專盃複賽,更加壓縮了原本的自由時段,所以這禮拜的自主學習計畫就只有完成了一半。

    Read more...

    第十六週回顧

    隨著新學期的開始,除了原本的自主學習計畫之外,又多出了幾個新的主題想要涉獵,有些是之前有簡短看過一點的,有些則是完全陌生的領域。最後我決定除了原本進行的這兩個課程之外,再另外加上兩個自學的支線,一個是UC Berkeley的Luca Trevisan教授在這學期開的Graph Partitioning, Expanders and Spectral Methods,另一個則是UIUC的Yihong Wu教授開的Information-theoretic methods in high-dimensional statistics。

    Read more...

    第十五週回顧

    這禮拜開始著手規劃撰寫計算理論相關的中文科普文章,約到了三位背景不太相似的朋友要在禮拜日幫我審閱試寫的四篇文章。希望可以先將目標的對象還有寫作風格確定下來,瞭解一下適合的文章內容、長度等。此外,我也簡單列出了可能的寫作大綱,目前計畫分成兩大部分,第一部份是基礎背景的介紹,讓原本對於資訊理論不熟的人,可以認識基本的概念和定義,這樣在第二部分的專題介紹中會更能抓住核心的蓋念。

    Read more...

    第十四週回顧

    這禮拜是期待已久的開學週,在台大的最後一個學期,修課數量明顯的減少,從以往大約5-7門的主科到這次只有三門,不過這三門都是我很熱愛而且扎實的課(有兩門課每週都有作業!)。此外還很幸運地選上咖啡學和音樂欣賞,看來這學期將會有充實的知識饗宴,又有豐富的感官享受!

    Read more...

    第十三週回顧

    經過兩個多月的努力,自主學習計畫的第一階段終於順利的如期完成了!看著一篇篇的筆記還有回顧心得,除了感嘆時間過得很快之外,也很替自己感到高興,能夠在期末考的壓力、全家出遊還有過年的外界誘惑下把預計的進度看完。這一個階段很多的教材是我在去年暑假就一直想要看,但是斷斷續續沒有完成的部分。透過這次自主學習計畫,一半靠自己的毅力還有一半的心理壓力,雖然中途有幾週延誤了進度,最後還是衝刺補了回來,算是達成了以前做不到的任務了吧!

    Read more...

    第十二週回顧

    才覺得寒假沒開始多久,農曆新年就緊接著來了,雖然這幾年越來越沒有像小時候那樣過節的氣氛,但是每年到了這個時候仍然都是最放鬆的時刻。今年春節的作息比較一致,每天起來吃個早餐開始唸一些書,泡完咖啡後再唸一下書,中午和家人聚餐吃飯聊聊天,午覺後再繼續唸書,晚上可能會看個電影或是影集,睡前再看看小說。生活被書本、食物和電影填滿了,三個都是我最喜歡做的事情,這樣的日子過得還真是愜意呀!

    Read more...

    第十一週回顧

    這禮拜計算理論和pseudoransomness的進度都分別來到最精彩的部份,前者進入「代數複雜度」(Algebraic complexity)的領域,目標是研究進行平時常見的代數運算所花費的計算複雜度,很神奇的是前人把這些看起來與電腦習慣使用的0,1位元運算做了很深刻了連結,提出了對應的複雜度類別,讓人們可以對最直接的數學運算做分析,不必再將問題轉換成電腦可以表達的方式。

    Read more...

    第十週回顧

    上禮拜結束所有的期末報告之後,正式來到了大學生涯最後一個寒假。雖然是個假期,但是對於準備要申請國外研究所的我來說,這是當兵前最後一個空擋好好為接下來的研究還有課業打穩腳步。除了持續進行原本的自主學習計畫之外,這段期間還多了一個重要的學習目標:代數。因為在幾個月前得知當我放棄雙主修數學系改成輔修之後,原本可以抵免系上的線性代數課程變成無法充兼數學系的輔系必選學分,也就是說我必修再多修一門代數相關的課程。為了要拿到數學系的輔系,我必須跳過代數導論上,直接挑戰下學期的代數導論下!之前聽幾個雙主修的同學聊過代數導論這門課,大家紛紛認為是一門很硬不容易讀的科目,看來下學期除了自己的研究之外,在修課方面也會面臨不小的挑戰。

    Read more...

    第九週回顧

    繼上週期末考造成進度拖累之後,這禮拜面對的是五天四夜的家庭旅遊,再加上禮拜五下午有一個期末口試和報告,自主學習計畫面臨嚴峻的考驗。

    Read more...

    第八週回顧

    當初在規劃進度的時候,特地設想到期末考中可能會有許多無法預期的事情發生,很可能沒辦法專心的學習新的範圍,因此故意把複習週排在這個時間點。而的確這禮拜因為一些煩心的事情,還有考試及meeting,進行的不是很順利。前四天下來,除了想了一些題目之外,幾乎沒有把之前的落後的進度補起來。再加上禮拜五回家、禮拜六投票日、禮拜日出發去家庭旅遊,即使在沒有多餘進度安排的情況之下,這禮拜的複習還是失敗了。

    Read more...

    Day 1: 彩虹、台東市、雨過天晴

    早上六點半,準時被媽媽叫醒,五天四夜的花東埔里之旅即將開始。

    Read more...

    第七週回顧

    期末考前的一個禮拜,是最輕鬆,也是最讓人無法專注好好把一件事情完成的一週。這次的進度來到了我之前就很有興趣的主題:互動式證明(Interactive Proofs)。在二十多年前,$\IP$(Interactive Proofs的一個複雜度類別)被證明出和PSPACE(多項式空間複雜度)等價時,正式宣告了相對化技術(relativization technique)的死刑,並且開創了一個新的可能,緊接著Arora也發表了著名的$\PCP$定理,利用互動式證明的概念,將$\NP$定位在$\PCP(\log n,1)$,讓人們一度以為有機會解決$\P$ vs. $\NP$的問題,不過二十年過去了,$\P$ vs. $\NP$仍然懸而未解,倒是互動式證明的概念帶起了許多近代密碼學重要的概念。

    Read more...

    第六週回顧

    2015 年的最後一個禮拜在放榜的緊張情緒,還有三連假的悠閒中度過了。公費留學考試在這幾年刻意將放榜的日子選在12/31號,就像大學指考的放榜選在父親節一樣,讓大家在特別的日子中面對人生中重要的結果出爐。

    Read more...

    第五週回顧

    隨著年底的到來,時間果2015 Xmas然過得特別快,事情也令人多的感覺做不完。這禮拜身邊歡樂的氣氛讓自己稍微鬆懈了一下,同時週末要回家一趟,事情將要無法順利做完是意料中的事。看著行事曆一排排的死線,心中又很想要一些別的東西,做一些別的事情,真是左右為難啊!

    Read more...

    第四週回顧

    這禮拜進入了自主學習者的第一個緩衝週,基本上因為進度都有跟上,所以這週大部份的時間都是花在做習題。然而事情沒有計畫的簡單,Pseudorandomness的習題大部份除了有很多小題之外,大多都需要一些全新的想法才有可能解得出來。像是第二章第九題的Spectral Graph Theory,那六個小題基本上就是那個領域最開始一些創新想法的簡單版,幾乎都需要一點點巧思才有可能解開。不過也因為如此,多少有訓練到自己看問題時的開放思維吧!

    Read more...

    第三週回顧

    這禮拜在不知不覺的匆匆忙忙中結束了,相對起來主動學習計畫的執行顯得比較慌亂一點,有超過一半的內容是邊吃飯邊看過的,習題大多也是在搭車的路上,或是騎腳踏車的時候想。該看的都還是有看完,不過就沒有時間好好整理一下,題目更是沒有完整的時間好好思考,這大概就是沒有排每週固定時間的下場吧!

    Read more...

    第二週回顧

    這禮拜是NTU Active Learner計畫的第二週,果然和預期的一樣仍然充滿了幹勁,不知道一個月後是否還能維持呢?

    Read more...

    第一週回顧

    這禮拜是NTU Active Learner計畫的第一個禮拜,整體看來都在進度上,同時也在禮拜一的時候架了這一個部落格,接下來一些學習的心得,還有計劃遇到的困難等等都會記錄在這邊。

    Read more...