$
\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}
$
Polynomials
Low degree extension
Let $\mathbb{F}$ be a field, $H,S\subseteq\mathbb{F}$ are subsets, and $f:H^m\rightarrow S$ for some $m\in\bbN$. Then there exists a $m$-variate polynomial $\tilde{f}:\mathbb{F}^m\rightarrow\mathbb{F}$ such that
- (low degree) the degree of $\tilde{f}$ in each variable is at most $h-1$ where $h=\card{H}$, and
- (extension) for any $x\in H^m$, $\tilde{f}(x)=f(x)$.
The idea is based on Lagrange’s interpolation. Denote the elements in $H$ as $H=\{a_1,\dots,a_h\}$, define $\tilde{f}$ as follows.
\begin{equation}
\tilde{f}(x) := \sum_{i_1,\dots i_m\in[h]}\phi(a_{i_1},\dots,a_{i_m})\prod_{t\in[m]}\frac{\prod_{j\neq i_t}(x_t-a_j)}{\prod_{j\neq i_t}a_{i_t}-a_j}.
\end{equation}
Clearly that the degree of $\tilde{f}$ in each variable is at most $h-1$. To check the second property, consider any $x\in H^m$, we have $x=(a_1,\dots,a_m)$ for some $a_i\in H$ for any $i\in[m]$. Then, by the definition of $\tilde{f}$, we have $\tilde{f}(x)=f(x)$.
Schwartz-Zippel lemma
Let $\mathbb{F}$ be a field and $S\subseteq\mathbb{F}$. For any degree $d$ nonzero $m$-variate polynomial $f$ over $\mathbb{F}$ for some $m\in\bbN^+$, we have
\begin{equation}
\mathbb{P}_{a_1,\dots,a_m\leftarrow S}[f(a_1,\dots,a_m)=0]\leq\frac{d}{\card{S}}.
\end{equation}
Let’s prove by induction on the number of variables. When $m=1$, as the number of roots of a degree $d$ nonzero polynomial is at most $d$, the inequality holds.
Suppose the inequality holds for degree less than $m$, rewrite $f(x_1,\dots,x_m)$ as follows.
\begin{equation}
f(x_1,\dots,x_m) = \sum_{i=0}^{\ell}f_i(x_2,\dots,x_m)x_1^i,
\end{equation}
where $f_i$ is a $(m-1)$-variate polynomial of degree at most $d-i$ and $\ell\leq d$. As a result, by the induction hypothesis, the probability that $f(x_1,a_2,\dots,a_m)$ is a zero polynomial can be upper bounded by $\frac{d-\ell}{\card{S}}$. Thus,
\begin{align}
&\mathbb{P}_{a_1,\dots,a_m\leftarrow S}[f(a_1,\dots,a_m)=0]\\
&= \mathbb{P}_{a_1\leftarrow S}[f(a_1,\dots,a_m)|f(\cdot,a_2,\dots,a_m)\text{ is nonzero}]\\
&\cdot\mathbb{P}_{a_2,\dots,a_m\leftarrow S}[f(\cdot,a_2,\dots,a_m)\text{ is nonzero}]\\
&+ \mathbb{P}_{a_1\leftarrow S}[f(a_1,\dots,a_m)|f(\cdot,a_2,\dots,a_m)\text{ is zero}]\\
&\cdot\mathbb{P}_{a_2,\dots,a_m\leftarrow S}[f(\cdot,a_2,\dots,a_m)\text{ is zero}]\\
&\leq \frac{\ell}{\card{S}}\cdot1+ 1\cdot\frac{d-\ell}{\card{S}}\\
&=\frac{d}{\card{S}}.
\end{align}
Composition techniques
Bundling polynomials into a single polynomial
Given polynomials $p_1,\dots,p_t:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ where $\mathbb{F}$ is a field and $\card{\mathbb{F}}\geq t$. Suppose each of the degree of the polynomials is at most $\alpha$, then there exists a polynomial $q:\mathbb{F}^{\ell+1}\rightarrow\mathbb{F}$ of degree at most $\alpha+t-1$ such that for any $i\in[t]$ and $z\in\mathbb{F}^{\ell}$, $q(i,z)=p_i(z)$.
Construct $q$ as follows. First, for each $i\in[t]$, define polynomial
\begin{equation}
\delta_{i}(x) := \prod_{j\neq i\in[t]}\frac{x-j}{i-j}.
\end{equation}
Namely, for any $i,j\in[t]$, $\delta_i(j)=\mathbf{1}_{i=j}$. Note that the degree of $\delta_i$ is at most $t-1$.
Next, define polynomial
\begin{equation}
q(x,z) := \sum_{i\in[t]}\delta_i(x)\cdot p_i(z).
\end{equation}
Note that the degree of $q$ is at most $\alpha+t-1$ and for any $i\in[t]$ and $z\in\mathbb{F}^{\ell}$, $q(i,z)=p_i(z)$, which is the goal of the lemma.
Low degree extension
Given a degree $d$ polynomial $p:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ and $H\subseteq\mathbb{F}$. Then there exists a polynomial $q$ of degree $\ell\cdot\card{H}$ such that $p$ is nonzero on $H^{\ell}$ iff $q$ is nonzero on $\mathbb{F}^{\ell}$.
Denote $H=\{h_1,\dots,h_{\card{H}}\}$. Define $p_1:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ as follows.
\begin{equation}
p_1(x_1,x_2,\dots,x_{\ell})=\sum_{t\in[\card{H}]}p(h_t,x_2,\dots,x_{\ell})\cdot x_1^t.
\end{equation}
Observe that $p$ is nonzero on $H^{\ell}$ iff $p_1$ is nonzero on $\mathbb{F}\times H^{\ell-1}$. Similarly, for $i=2,\dots,\ell$, define $p_i:\mathbb{F}^{\ell}\rightarrow\mathbb{F}$ as follows.
\begin{equation}
p_{i}(x_1,x_2,\dots,x_{\ell})=\sum_{t\in[\card{H}]}p(x_1,\dots,x_{i-1},h_t,\dots,x_{\ell})\cdot x_i^t.
\end{equation}
Thus, we have $p$ is nonzero on $H^{\ell}$ iff $p_i$ is nonzero on $\mathbb{F}^{i}\times H^{\ell- i}$. Take $q=p_{\ell}$
Also, by the construction, for each $i\in[\ell]$, the degree of $x_i$ in $q$ is at most $\card{H}$. Thus, the total degree of $q$ is at most $\ell\cdot\card{H}$.
Local characterizations
Local characterizations of polynomials are useful tools for property testing in which one can test whether an oracle is close to a low degree polynomial. Intuitively, as a global property is equivalent to a set of local properties, by probabilistically checking whether the oracle satisfies an random local property, one can infer the closeness of the oracle having that property. See this note for details.
Local characterizations of multivariate polynomial
Let $\mathbb{F}$ be a field and $f$ be a $m$-variate polynomial over $\mathbb{F}$ where $\card{\mathbb{F}}>2d$. $f$ is of degree at most $d$ iff for any line $L_{\bs,\bh}:=\{f(\bs+t\cdot \bh)\}_{t\in\mathbb{F}}$, where $\bs,\bh\in\mathbb{F}^m$, is a polynomial of degree at most $d$ in $i$.
In the following, denote $f_{\bs,\bh}(t)=f(\bs+t\cdot\bh)$ for any $\bs,\bh\in\mathbb{F}$ and $t\in\mathbb{F}$.
- ($\Rightarrow$) This direction is trivial. For any $\bs,\bh\in\mathbb{F}$ and $t\in\mathbb{F}$, we have $f(\bs+t\cdot \bh)=f(\bs_1+t\cdot\bh_1,\dots,\bs_m+t\cdot\bh_m)$. As the degree of the $i$th coordinate is the same as the degree of $(\bs_i+t\cdot\bh_i)$ for any $i\in[m]$, the total degree of $t$ in $f_{\bs,\bh}(t)$ is the same as the total degree of $f$, which is at most $d$.
- ($\Leftarrow$) This direction is proved by induction on the number of variables and Schwartz-Zippel lemma.
For the base case, clearly that the statement holds for univariate polynomial. Suppose the statement holds for $(m-1)$-variate polynomial, consider the following.
First, we can yield the following loose upper bound on the degree of $f$ by the induction hypothesis.
Suppose the local characterization lemma holds for polynomials with at most $m-1$ variables. For any $\bs,\bh\in\mathbb{F}^m$, $L_{\bs,\bh}$ is a polynomial of degree at most $d$, then the degree of $f$ is at most $2d$.
For any $\bx\in\mathbb{F}^{m-1}$, let $\bh=(\bx,0)$, we have $f_{\mathbf{0},\bh}$ is polynomial of degree at most $d$ by the assumption. Specifically, we can rewrite $f$ as follows.
\begin{equation}
f(x_1,\dots,x_m) = \sum_{a=0}^{d}f(x_1,\dots,x_{m-1},a)\delta_a{x_m},
\end{equation}
where $\delta_a$ is the degree $d$ polynomial such that $\delta_{a}(a’)=\mathbf{1}_{a=a’}$ for any $a,a’\in\{0,1,\dots,d\}$.
As $f(x_1,\dots,x_{m-1},a)$ also satisfies the assumption and only has $m-1$ variables for any $a\in\{0,1,\dots,d\}$, by the induction hypothesis, $f(x_1,\dots,x_{m-1},a)$ is of degree at most $d$. Thus, the degree of $f$ is at most $2d$.
With the above loose upper bound, we can use the Schwartz-Zippel lemma to show that the degree of $f$ is the same as the degree of $f_{\mathbf{0},\bh}$ for some $\bh\in\mathbb{F}^m$.
Suppose the degree of $f$ is at most $2d$ and $\card{\mathbb{F}}>2d$, then there exists $\bh\in\mathbb{F}^m$ such that $\text{deg}(f)=\text{deg}(f_{\mathbf{0},\bh})$.
Observe that
\begin{equation}
f_{\mathbf{0},\bh}(t)=f(t\cdot\bh_1,\dots,t\cdot\bh_m)=\sum_{i=0}^{\text{deg}(f)}f_i(\bh)t^i,
\end{equation}
where $f_i$ is a polynomial of degree at most $2d$ by the above loos upper bound. Note that the degree of $h_{\mathbf{0},\bh}$ is the largest $i$ such that $f_i(\bh)$ is nonzero. As a result, the probability of $\text{deg}(f_{\mathbf{0},\bh})=\text{deg}(f)$ can be lower bounded by the probability of $f_{\text{deg}(f)}(\bh)$ not being zero.
\begin{align}
\mathbb{P}_{\bh}[\text{deg}(f_{\mathbf{0},\bh})=\text{deg}(f)]&=\mathbb{P}_{\bh}[f_{\text{deg}(f)}(\bh)\neq0]\\
&>1-\frac{2d}{\card{\mathbb{F}}}>0.
\end{align}
Thus, by the probabilistic argument, we know that there exists $\bh\in\mathbb{F}^m$ such that $\text{deg}(f)=\text{deg}(f_{\mathbf{1},\bh})$.
Finally, by the assumption, for any $\bh\in\mathbb{F}^m$, $\text{deg}(f_{\mathbf{0},\bh})\leq d$. Thus, directly from the above claim, we have $\text{deg}(f)\leq d$.
Local characterization of univariate polynomial
Let $\mathbb{F}$ be a field and $1\leq d<\card{\mathbb{F}}+1$. There exists $e_1,\dots,e_{d+1},\alpha_1,\dots,\alpha_{d+1}\in\mathbb{F}$ such that for any univariate polynomial $f:\mathbb{F}\rightarrow\mathbb{F}$ of degree at most $d$ and $x,h\in\mathbb{F}$ we have
\begin{equation}
f(x) = \sum_{i\in[d+1]}\alpha_i\cdot f(x+e_i\cdot h).
\end{equation}
Here we only prove the special case where $\mathbb{F}$ is a prime field. Basically, for general fields, the ideas are the same.
For prime field, we’ll take $e_i=i$ and $\alpha_i=(-1)^{i+1}\binom{d+1}{i}$ for any $i\in[d+1]$.
Let’s prove by induction on $d$. Clearly that when $f$ is a constant function, i.e., $d=0$, we have $f(x)=f(x+h)$ for any $x,h\in\mathbb{F}$. Now, suppose that the statement holds for polynomial of degree less than $d$.
Consider the derivative of $f$: $f’$, which is defined as $f’(x):=f(x+1)-f(x)$ for any $x\in\mathbb{F}$. For any $x\in\mathbb{F}$, we can rewrite $f(x)$ as
\begin{equation}
f(x) = f(x+1)-f’(x).
\end{equation}
By induction hypothesis, we have
\begin{align}
f’(x) &= \sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f’(x+i)\\
&= \sum_{i=1}^d(-1)^{i+1}\binom{d}{i}\Big(f(x+i+1)-f(x+i)\Big)\\
&= -\sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f(x+i) - \sum_{i=2}^{d+1}(-1)^{i+1}\binom{d}{i-1}f(x+i).
\end{align}
Combine the above two equations we have
\begin{align}
f(x) &= f(x+1)+\sum_{i=1}^d(-1)^{i+1}\binom{d}{i}f(x+i)+\sum_{i=2}^{d+1}(-1)^{i+1}\binom{d}{i-1}f(x+i)\\
&=\sum_{i=1}^d(-1)^{i+1}[\binom{d}{i}+\binom{d}{i-1}]f(x+i) + (-1)^{d+2}\binom{d}{d}f(x+d+1)\\
&=\sum_{i=1}^{d+1}(-1)^{i+1}\binom{d+1}{i}f(x+i).
\end{align}
Identities
Newton identity
Newton identity provides a bridge between $\Sym_k$ and $\Pow_k$. For our interest in arithmetic circuits, Newton identity tells us that $\Sym_d$ has a $\Sigma\Pi\Sigma\Lambda$ circuit of size $2^{O(\sqrt{d})}\cdot\poly(n)$. Note that the resulting circuit is homogeneous. Recall that there is $n^{\Omega(d)}$ lower bound for $\Sigma\Lambda\Sigma$ circuits computing $\Sym_d$.
For any $k\in[n]$, we have
\begin{eqnarray*}
\Sym_k &=\frac{1}{k!}
\begin{vmatrix}
\Pow_1 & 1 & 0 & \cdots & 0 \\
\Pow_2 & \Pow_1 & 2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \cdots & 0 \\
\Pow_{k-1} & \Pow_{k-2} & \cdots & \Pow_1 & k-1 \\
\Pow_k & \Pow_{k-1} & \cdots & \Pow_2 & \Pow_1
\end{vmatrix}.
\end{eqnarray*}
Specifically, one can write $x_1x_2\cdots x_k=\sum_{\mathbf{a}:\ \sum_iia_i=k}\alpha_{\mathbf{a}}(\Pow_1)^{a_1}(\Pow_2)^{a_2}\cdots(\Pow_k)^{a_k}$.
Applications:
- Any non-homogeneous $\Sigma\Pi\Sigma$ circuit can be converted to homogeneous $\Sigma\Pi\Sigma\Lambda\Sigma$ circuit with $2^{O(\sqrt{d})}\cdot\poly(n)$ blow-up.
Ryser-Fischer identity
Ryser-Fischer identity expresses multilinear monomial into sums of the power of sum. To our interest in arithmetic circuits, it implies that one can replace monomial $x_1x_2\cdots c_d$ with a size $2^d$ $\Sigma\Lambda\Sigma$ circuit. Note that the circuit is homogeneous.
For any $d\in\N$, we have
\begin{equation*}
x_1x_2\cdots x_d = \sum_{S\subseteq[d]}(-1)^{d-\card{S}}(\sum_{i\in S}x_i)^d.
\end{equation*}
The proof is based on simple inclusion-exclusion principle so here we omit the details.
Approximation theory
Symmetrization
Symmetrization by Minsky and Papert had been used to prove the first few approximate degree lower bound and sign rank lower bound. The basic idea is turning a multivariate symmetric polynomial over the boolean cube to a univariate polynomial over $\bbR$ without increasing the degree. Formally, it can be stated as foloows.
Let $p:\bit^n\rightarrow\bbR$ be a symmetric polynomial of degree $d$. Then, there exists an univariate polynomial $q:\bbR\rightarrow\bbR$ of degree at most $d$ such that for all $x\in\bit^n$,
\begin{equation*}
p(x) = q(\card{x}),
\end{equation*}
where $\card{x}$ is defined as the number of 1 in $x$.
There’s also a generalization which is useful in some applications such as the sign rank lower bound of Razborov-Sherstov for depth-3 $\AC{0}$ function.
Let $p:\bit^n\rightarrow\bbR$ be a block-symmetric polynomial of degree $d$ with blocks $B_1,B_2,\dots,B_k$. Then there exists a $k$-variate polynomial $q:\bbR^k\rightarrow\bbR$ of degree at most $d$ such that for all $x\in\bit^n$,
\begin{equation*}
p(x) = q(\card{x_{B_1}},\card{x_{B_2}},\cdots,\card{x_{B_k}}),
\end{equation*}
Ehlich-Zeller and Rivlin-Cheney theorem
The Ehlich-Zeller and Rivlin-Cheney theorem gives a qualitative description for the intuition that low-degree polynomial cannot simultaneously have large gradient while concentrate in an interval. It has applications in quantum query complexity and threshold circuits lower bound. There are several versions and here we start from one of the most user-friendly one.
For any $a>0$ and $k\in\N$. Let $p:\bbR\rightarrow\bbR$ be a degree $d<\sqrt{k}$ polynomial such that $p(0)\geq a$ and $p(i)\leq0$ for all $i\in[k]$. Then, there exists an $i\in[k]$ such that $p(i)\leq2a$.
Note that the above polynomial can be shifted to $p(0)\neq0$ or changed sign. The only requirement is a gap betweeen the value of $p(0)$ and $p(i)$. The following is the full version of the full version of Ehlich-Zeller and Rivlin-Cheney theorem.
For any $a<b$, $c>0$, and $k\in\N$. Let $p:\bbR\rightarrow\bbR$ be a polynomial such that $p(i)\in[a,b]$ for any $i=0,1,\dots,k$ and there exists $x\in[a,b]$ such that $p’(x)\geq c$. Then, the degree of $p$ is at least $\sqrt{\frac{ck}{c+b-a}}$.
Recommended lecture notes/survey