A Technique for Hardness Amplification Against $\mathsf{AC}^0$

We study hardness amplification in the context of two well-known "moderate" average-case hardness results for $\mathsf{AC}^0$ circuits. First, we investigate the extent to which $\mathsf{AC}^0$ circuits of depth $d$ can approximate $\mathsf{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 $\mathsf{AC}^0_{d + k}$ circuit $h \colon \{0, 1\}^n \to \{0, 1\}$ such that for every $\mathsf{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 $\mathsf{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 $\mathsf{MAJ}_n^{\oplus t}$. We show that if $g$ is an $\mathsf{AC}^0_d$ circuit of size $S$, then $g$ agrees with $\mathsf{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 $\mathsf{AC}^0$ circuits is to (a) design some distribution over random restrictions or random projections, (b) show that $\mathsf{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.

This paper is about the value of time for computation. If we slightly increase our time budget, how much extra computational power do we gain?

To be more specific, we study a model of fast parallel algorithms called "$\mathsf{AC}^0$ circuits." An $\mathsf{AC}^0$ circuit is a network of AND gates, OR gates, NOT gates, and input variables connected by wires. You can assign binary values to the input variables. The values feed into whatever gates are connected to the variables. The outputs of those gates feed into other gates, which feed into other gates, and so on, until eventually the circuit produces a binary output. The "depth" of the circuit is the maximum number of AND and OR gates on any path from an input variable to the output gate, which can be considered a measure of the amount of time that the computation takes. The "size" of the circuit is the total number of AND and OR gates, which is a measure of the total amount of work that goes into the computation.

In the paper, we show that for every $d$, there is a computational problem such that on the one hand, the problem can be solved by small $\mathsf{AC}^0$ circuits of depth $d + 3$, but on the other hand, the problem cannot be solved by $\mathsf{AC}^0$ circuits of depth $d$ unless they are enormous. In fact, depth-$d$ circuits that are trying to solve this problem and that are not enormous cannot achieve a success rate significantly better than random guessing. Theorems along these lines have been proven previously, but our bound on the success rate is better than the previous bounds.