<div dir="ltr">Hi all — please join us <b>today at 12:30pm</b> for another theory lunch! Details below.<div><br></div><div>******</div><div><b>Date:</b> January 31, 2024</div><div><b>Time: </b>12:30pm CT</div><div><b>Location:</b> JCL 390</div><div><br></div><div><b>Title: </b>A Technique for Hardness Amplification Against <img alt="\mathrm{AC}^0" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.27132322420559696" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"></div><div><b><br></b></div><div><b>Speaker:</b> William Hoza (UChicago)</div><div><br></div><div><b>Abstract:</b> We study hardness amplification in the context of two well-known "moderate" average-case hardness results for <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.47842528461111433" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits. First, we investigate the extent to which <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.17845627273098041" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits of depth <img alt="d" title="d" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=d" id="m_294510167671532388l0.29679465109092584" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> can approximate <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.6029925111375238" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits of some larger depth <img alt="d + k" title="d + k" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=d%09%2B%09k" id="m_294510167671532388l0.7454760593552725" height="12" width="36" class="gmail-CToWUd" style="display: inline; vertical-align: -1.333px;">. The case <img alt="k = 1" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=k%09=%091" id="m_294510167671532388l0.8605448200286203" height="11" width="37" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> is resolved by Håstad, Rossman, Servedio, and Tan's celebrated average-case depth hierarchy theorem (JACM 2017). Our contribution is a significantly stronger correlation bound when <img alt="k \geq 3" title="k \geq 3" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=k%09%5Cgeq%093" id="m_294510167671532388l0.20296434379707273" height="13" width="37" class="gmail-CToWUd" style="display: inline; vertical-align: -2.333px;">. Specifically, we show that there exists a linear-size <img alt="\mathrm{AC}^0_{d + k}" title="\mathrm{AC}^0_{d + k}" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0%5F%7Bd%09%2B%09k%7D" id="m_294510167671532388l0.7468916552860456" height="19" width="43" class="gmail-CToWUd" style="display: inline; vertical-align: -5.333px;"> circuit <img alt="h \colon \{0, 1\}^n \to \{0, 1\}" title="h \colon \{0, 1\}^n \to \{0, 1\}" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h%09%5Ccolon%09%5C%7B0,%091%5C%7D%5En%09%5Cto%09%5C%7B0,%091%5C%7D" id="m_294510167671532388l0.9849991132097291" height="16" width="133" class="gmail-CToWUd" style="display: inline; vertical-align: -4.333px;"> such that for every <img alt="\mathrm{AC}^0_d" title="\mathrm{AC}^0_d" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0%5Fd" id="m_294510167671532388l0.45069601409407456" height="18" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -4px;"> circuit <img alt="g" title="g" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="m_294510167671532388l0.1668554447184305" height="10" width="7" class="gmail-CToWUd" style="display: inline; vertical-align: -3.667px;">, either <img alt="g" title="g" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="m_294510167671532388l0.7588558617140901" height="10" width="7" class="gmail-CToWUd" style="display: inline; vertical-align: -3.667px;"> has size <img alt="\exp(n^{\Omega(1/d)})" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cexp(n%5E%7B%5COmega(1/d)%7D)" id="m_294510167671532388l0.6984163809158535" height="18" width="81" class="gmail-CToWUd" style="display: inline; vertical-align: -4.333px;">, or else <img alt="g" title="g" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="m_294510167671532388l0.9005115277775686" height="10" width="7" class="gmail-CToWUd" style="display: inline; vertical-align: -3.667px;"> agrees with <img alt="h" title="h" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="m_294510167671532388l0.5947896757801487" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> on at most a <img alt="(1/2 + \varepsilon)" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=(1/2%09%2B%09%5Cvarepsilon)" id="m_294510167671532388l0.06443833957765466" height="16" width="61" class="gmail-CToWUd" style="display: inline; vertical-align: -4.333px;">-fraction of inputs where <img alt="\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cvarepsilon%09=%09%5Cexp(-(1/d)%09%5Ccdot%09%5COmega(%5Clog%09n)%5E%7Bk%09-%091%7D)" id="m_294510167671532388l0.8025909306987313" height="17" width="207" class="gmail-CToWUd" style="display: inline; vertical-align: -4.333px;">. For comparison, Håstad, Rossman, Servedio, and Tan's result has <img alt="\varepsilon = n^{-\Theta(1/d)}" title="\varepsilon = n^{-\Theta(1/d)}" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cvarepsilon%09=%09n%5E%7B-%5CTheta(1/d)%7D" id="m_294510167671532388l0.006551543541361005" height="14" width="82" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;">. Second, we consider the majority function. It is well known that the majority function is moderately hard for <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.23674427729729253" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of <img alt="t" title="t" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=t" id="m_294510167671532388l0.38266487365827473" height="10" width="5" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> copies of the <img alt="n" title="n" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=n" id="m_294510167671532388l0.08164473932557259" height="7" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;">-bit majority function, denoted <img alt="\mathrm{MAJ}_n^{\oplus t}" title="\mathrm{MAJ}_n^{\oplus t}" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BMAJ%7D%5Fn%5E%7B%5Coplus%09t%7D" id="m_294510167671532388l0.7644836895691762" height="17" width="47" class="gmail-CToWUd" style="display: inline; vertical-align: -4px;">. We show that if <img alt="g" title="g" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="m_294510167671532388l0.26642003669407965" height="10" width="7" class="gmail-CToWUd" style="display: inline; vertical-align: -3.667px;"> is an <img alt="\mathrm{AC}^0_d" title="\mathrm{AC}^0_d" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0%5Fd" id="m_294510167671532388l0.06491665800901147" height="18" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -4px;"> circuit of size <img alt="S" title="S" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=S" id="m_294510167671532388l0.276993815574867" height="11" width="9" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;">, then <img alt="g" title="g" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="m_294510167671532388l0.7108545863407483" height="10" width="7" class="gmail-CToWUd" style="display: inline; vertical-align: -3.667px;"> agrees with <img alt="\mathrm{MAJ}_n^{\oplus t}" title="\mathrm{MAJ}_n^{\oplus t}" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BMAJ%7D%5Fn%5E%7B%5Coplus%09t%7D" id="m_294510167671532388l0.544283017509668" height="17" width="47" class="gmail-CToWUd" style="display: inline; vertical-align: -4px;"> on at most a <img alt="(1/2 + \varepsilon)" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=(1/2%09%2B%09%5Cvarepsilon)" id="m_294510167671532388l0.6664267003234907" height="16" width="61" class="gmail-CToWUd" style="display: inline; vertical-align: -4.333px;">-fraction of inputs, where <img alt="\varepsilon = \left(n^{-1/2} \cdot O(\log S)^{d - 1} \cdot \sqrt{\log n}\right)^t" title="" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cvarepsilon%09=%09%5Cleft(n%5E%7B-1/2%7D%09%5Ccdot%09O(%5Clog%09S)%5E%7Bd%09-%091%7D%09%5Ccdot%09%5Csqrt%7B%5Clog%09n%7D%5Cright)%5Et" id="m_294510167671532388l0.9177252005618342" height="22" width="238" class="gmail-CToWUd" style="display: inline; vertical-align: -6px;">.</div><div><br></div><div>To prove these results, we develop a hardness amplification technique that is tailored to a specific type of circuit lower bound proof. In particular, one way to show that a function <img alt="h" title="h" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="m_294510167671532388l0.6418678335991894" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> is moderately hard for <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.9158575134924405" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits is to (a) design some distribution over random restrictions or random projections, (b) show that <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm%7BAC%7D%5E0" id="m_294510167671532388l0.9385177783665621" height="14" width="28" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, <img alt="h" title="h" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="m_294510167671532388l0.6012021070265205" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if <img alt="h" title="h" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="m_294510167671532388l0.11322980622622203" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of <img alt="h" title="h" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="m_294510167671532388l0.26540598594356224" height="11" width="8" class="gmail-CToWUd" style="display: inline; vertical-align: -0.333px;"> amplifies its hardness. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.</div><div><br></div><div>Preprint: <a href="https://eccc.weizmann.ac.il/report/2023/176/" target="_blank">https://eccc.weizmann.ac.il/report/2023/176/</a></div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>