We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $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 $k \geq 3$. Specifically, we show that there exists a linear-size $\mathrm{AC}^0_{d + k}$ circuit $h \colon \{0, 1\}^n \to \{0, 1\}$ such that for every $\mathrm{AC}^0_d$ circuit $g$, either $g$ has size $\exp(n^{\Omega(1/d)})$, or else $g$ agrees with $h$ on at most a $(1/2 + \varepsilon)$-fraction of inputs where $\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})$. For comparison, Håstad, Rossman, Servedio, and Tan's result has $\varepsilon = n^{-\Theta(1/d)}$. Second, we consider the majority function. It is well known that the majority function is moderately hard for $\mathrm{AC}^0$ circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of $t$ copies of the $n$-bit majority function, denoted $\mathrm{MAJ}_n^{\oplus t}$. We show that if $g$ is an $\mathrm{AC}^0_d$ circuit of size $S$, then $g$ agrees with $\mathrm{MAJ}_n^{\oplus t}$ on at most a $(1/2 + \varepsilon)$-fraction of inputs, where $\varepsilon = \left(O(\log S)^{d - 1} / \sqrt{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 $h$ is moderately hard for $\mathrm{AC}^0$ circuits is to (a) design some distribution over random restrictions or random projections, (b) show that $\mathrm{AC}^0$ circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, $h$ is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if $h$ can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of $h$ amplifies its hardness. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.

The correlation bound for the XOR-of-Majority function is stronger now.

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $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 $k \geq 3$. Specifically, we show that there exists a linear-size $\mathrm{AC}^0_{d + k}$ circuit $h \colon \{0, 1\}^n \to \{0, 1\}$ such that for every $\mathrm{AC}^0_d$ circuit $g$, either $g$ has size $\exp(n^{\Omega(1/d)})$, or else $g$ agrees with $h$ on at most a $(1/2 + \varepsilon)$-fraction of inputs where $\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})$. For comparison, Håstad, Rossman, Servedio, and Tan's result has $\varepsilon = n^{-\Theta(1/d)}$. Second, we consider the majority function. It is well known that the majority function is moderately hard for $\mathrm{AC}^0$ circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of $t$ copies of the $n$-bit majority function, denoted $\mathrm{MAJ}_n^{\oplus t}$. We show that if $g$ is an $\mathrm{AC}^0_d$ circuit of size $S$, then $g$ agrees with $\mathrm{MAJ}_n^{\oplus t}$ on at most a $(1/2 + \varepsilon)$-fraction of inputs, where $\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 $h$ is moderately hard for $\mathrm{AC}^0$ circuits is to (a) design some distribution over random restrictions or random projections, (b) show that $\mathrm{AC}^0$ circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, $h$ is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if $h$ can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of $h$ amplifies its hardness. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.

Minor improvements to the presentation

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathrm{AC}^0$ circuits. First, we investigate the extent to which $\mathrm{AC}^0$ circuits of depth $d$ can approximate $\mathrm{AC}^0$ circuits of some larger depth $d + k$. The case $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 $k \geq 3$. Specifically, we show that there exists a linear-size $\mathrm{AC}^0_{d + k}$ circuit $h \colon \{0, 1\}^n \to \{0, 1\}$ such that for every $\mathrm{AC}^0_d$ circuit $g$, either $g$ has size $\exp(n^{\Omega(1/d)})$, or else $g$ agrees with $h$ on at most a $(1/2 + \varepsilon)$-fraction of inputs where $\varepsilon = \exp(-(1/d) \cdot \Omega(\log n)^{k - 1})$. For comparison, Håstad, Rossman, Servedio, and Tan's result has $\varepsilon = n^{-\Theta(1/d)}$. Second, we consider the majority function. It is well known that the majority function is moderately hard for $\mathrm{AC}^0$ circuits (and stronger classes). Our contribution is a stronger correlation bound for the XOR of $t$ copies of the $n$-bit majority function, denoted $\mathrm{MAJ}_n^{\oplus t}$. We show that if $g$ is an $\mathrm{AC}^0_d$ circuit of size $S$, then $g$ agrees with $\mathrm{MAJ}_n^{\oplus t}$ on at most a $(1/2 + \varepsilon)$-fraction of inputs, where $\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 $h$ is moderately hard for $\mathrm{AC}^0$ circuits is to (a) design some distribution over random restrictions or random projections, (b) show that $\mathrm{AC}^0$ circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, $h$ is moderately hard for shallow decision trees with respect to an appropriate distribution. We show that if $h$ can be proven to be moderately hard by a proof with that structure, then XORing multiple copies of $h$ amplifies its hardness. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.