<div dir="ltr">Hi all — please join us <b>this Wednesday</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="" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.27132322420559696" height="14" style="display: inline; vertical-align: -0.333px;" width="28"></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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.47842528461111433" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> circuits. First, we investigate the extent to which <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.17845627273098041" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> circuits of depth <img alt="d" title="d" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=d" id="l0.29679465109092584" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> can approximate <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.6029925111375238" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> circuits of some larger depth <img alt="d + k" title="d + k" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=d%09%2B%09k" id="l0.7454760593552725" style="display: inline; vertical-align: -1.333px;" height="12" width="36">. The case <img alt="k = 1" title="k = 1" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=k%09=%091" id="l0.8605448200286203" style="display: inline; vertical-align: -0.333px;" height="11" width="37"> 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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=k%09%5Cgeq%093" id="l0.20296434379707273" style="display: inline; vertical-align: -2.333px;" height="13" width="37">. Specifically, we show that there exists a linear-size <img alt="\mathrm{AC}^0_{d + k}" title="\mathrm{AC}^0_{d + k}" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0%5F{d%09%2B%09k}" id="l0.7468916552860456" style="display: inline; vertical-align: -5.333px;" height="19" width="43"> circuit <img alt="h \colon \{0, 1\}^n \to \{0, 1\}" title="h \colon \{0, 1\}^n \to \{0, 1\}" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h%09%5Ccolon%09%5C{0,%091%5C}%5En%09%5Cto%09%5C{0,%091%5C}" id="l0.9849991132097291" style="display: inline; vertical-align: -4.333px;" height="16" width="133"> such that for every <img alt="\mathrm{AC}^0_d" title="\mathrm{AC}^0_d" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0%5Fd" id="l0.45069601409407456" style="display: inline; vertical-align: -4px;" height="18" width="28"> circuit <img alt="g" title="g" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="l0.1668554447184305" style="display: inline; vertical-align: -3.667px;" height="10" width="7">, either <img alt="g" title="g" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="l0.7588558617140901" style="display: inline; vertical-align: -3.667px;" height="10" width="7"> has size <img alt="\exp(n^{\Omega(1/d)})" title="\exp(n^{\Omega(1/d)})" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cexp(n%5E{%5COmega(1/d)})" id="l0.6984163809158535" style="display: inline; vertical-align: -4.333px;" height="18" width="81">, or else <img alt="g" title="g" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="l0.9005115277775686" style="display: inline; vertical-align: -3.667px;" height="10" width="7"> agrees with <img alt="h" title="h" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="l0.5947896757801487" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> on at most a <img alt="(1/2 + \varepsilon)" title="" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=(1/2%09%2B%09%5Cvarepsilon)" id="l0.06443833957765466" style="display: inline; vertical-align: -4.333px;" height="16" width="61">-fraction of inputs where <img alt="\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})" title="\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})" class="va_li" 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{k%09-%091})" id="l0.8025909306987313" style="display: inline; vertical-align: -4.333px;" height="17" width="207">. For comparison, Håstad, Rossman, Servedio, and Tan's result has <img alt="\varepsilon = n^{-\Theta(1/d)}" title="\varepsilon = n^{-\Theta(1/d)}" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cvarepsilon%09=%09n%5E{-%5CTheta(1/d)}" id="l0.006551543541361005" style="display: inline; vertical-align: -0.333px;" height="14" width="82">. 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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.23674427729729253" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of <img alt="t" title="t" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=t" id="l0.38266487365827473" style="display: inline; vertical-align: -0.333px;" height="10" width="5"> copies of the <img alt="n" title="n" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=n" id="l0.08164473932557259" style="display: inline; vertical-align: -0.333px;" height="7" width="8">-bit majority function, denoted <img alt="\mathrm{MAJ}_n^{\oplus t}" title="\mathrm{MAJ}_n^{\oplus t}" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{MAJ}%5Fn%5E{%5Coplus%09t}" id="l0.7644836895691762" style="display: inline; vertical-align: -4px;" height="17" width="47">. We show that if <img alt="g" title="g" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="l0.26642003669407965" style="display: inline; vertical-align: -3.667px;" height="10" width="7"> is an <img alt="\mathrm{AC}^0_d" title="\mathrm{AC}^0_d" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0%5Fd" id="l0.06491665800901147" style="display: inline; vertical-align: -4px;" height="18" width="28"> circuit of size <img alt="S" title="S" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=S" id="l0.276993815574867" style="display: inline; vertical-align: -0.333px;" height="11" width="9">, then <img alt="g" title="g" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=g" id="l0.7108545863407483" style="display: inline; vertical-align: -3.667px;" height="10" width="7"> agrees with <img alt="\mathrm{MAJ}_n^{\oplus t}" title="\mathrm{MAJ}_n^{\oplus t}" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{MAJ}%5Fn%5E{%5Coplus%09t}" id="l0.544283017509668" style="display: inline; vertical-align: -4px;" height="17" width="47"> on at most a <img alt="(1/2 + \varepsilon)" title="(1/2 + \varepsilon)" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=(1/2%09%2B%09%5Cvarepsilon)" id="l0.6664267003234907" style="display: inline; vertical-align: -4.333px;" height="16" width="61">-fraction of inputs, where <img alt="\varepsilon = \left(n^{-1/2} \cdot O(\log S)^{d - 1} \cdot \sqrt{\log n}\right)^t" title="\varepsilon = \left(n^{-1/2} \cdot O(\log S)^{d - 1} \cdot \sqrt{\log n}\right)^t" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cvarepsilon%09=%09%5Cleft(n%5E{-1/2}%09%5Ccdot%09O(%5Clog%09S)%5E{d%09-%091}%09%5Ccdot%09%5Csqrt{%5Clog%09n}%5Cright)%5Et" id="l0.9177252005618342" style="display: inline; vertical-align: -6px;" height="22" width="238">.</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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="l0.6418678335991894" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> is moderately hard for <img alt="\mathrm{AC}^0" title="\mathrm{AC}^0" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.9158575134924405" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> 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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=%5Cmathrm{AC}%5E0" id="l0.9385177783665621" style="display: inline; vertical-align: -0.333px;" height="14" width="28"> 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" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="l0.6012021070265205" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if <img alt="h" title="h" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="l0.11322980622622203" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of <img alt="h" title="h" class="va_li" src="https://s0.wp.com/latex.php?zoom=3&bg=ffffff&fg=000000&s=0&latex=h" id="l0.26540598594356224" style="display: inline; vertical-align: -0.333px;" height="11" width="8"> 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>