[Theory] [Theory Lunch] William Hoza, Wednesday 1/31 12:30-1:30pm, JCL 390

[Gabe Schoenbach]

Hi all — please join us *this Wednesday* for another theory lunch! Details
below.

******
*Date:* January 31, 2024
*Time: *12:30pm CT
*Location:* JCL 390

*Title: *A Technique for Hardness Amplification Against [image:
\mathrm{AC}^0]

*Speaker:* William Hoza (UChicago)

*Abstract:* We study hardness amplification in the context of two
well-known "moderate" average-case hardness results for [image:
\mathrm{AC}^0] circuits. First, we investigate the extent to which [image:
\mathrm{AC}^0] circuits of depth [image: d] can approximate [image:
\mathrm{AC}^0] circuits of some larger depth [image: d + k]. The case [image:
k = 1] 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 [image: k \geq 3].
Specifically, we show that there exists a linear-size [image:
\mathrm{AC}^0_{d + k}] circuit [image: h \colon \{0, 1\}^n \to \{0, 1\}]
such that for every [image: \mathrm{AC}^0_d] circuit [image: g], either [image:
g] has size [image: \exp(n^{\Omega(1/d)})], or else [image: g] agrees
with [image:
h] on at most a [image: (1/2 + \varepsilon)]-fraction of inputs where [image:
\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})]. For comparison,
Håstad, Rossman, Servedio, and Tan's result has [image: \varepsilon =
n^{-\Theta(1/d)}]. Second, we consider the majority function. It is well
known that the majority function is moderately hard for [image:
\mathrm{AC}^0] circuits (and stronger classes). Our contribution is a
stronger correlation bound for the XOR of [image: t] copies of the [image:
n]-bit majority function, denoted [image: \mathrm{MAJ}_n^{\oplus t}]. We
show that if [image: g] is an [image: \mathrm{AC}^0_d] circuit of size [image:
S], then [image: g] agrees with [image: \mathrm{MAJ}_n^{\oplus t}] on at
most a [image: (1/2 + \varepsilon)]-fraction of inputs, where [image:
\varepsilon = \left(n^{-1/2} \cdot O(\log S)^{d - 1} \cdot \sqrt{\log
n}\right)^t].

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 [image: h] is moderately hard for [image:
\mathrm{AC}^0] circuits is to (a) design some distribution over random
restrictions or random projections, (b) show that [image: \mathrm{AC}^0]
circuits simplify to shallow decision trees under these
restrictions/projections, and finally (c) show that after applying the
restriction/projection, [image: h] is moderately hard for shallow decision
trees with respect to an appropriate distribution. We show that (roughly
speaking) if [image: h] can be proven to be moderately hard by a proof with
that structure, then XORing multiple copies of [image: h] amplifies its
hardness. Our analysis involves a new kind of XOR lemma for decision trees,
which might be of independent interest.

Preprint: https://eccc.weizmann.ac.il/report/2023/176/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240129/42f1d8a9/attachment-0001.html>