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

Abstract To show that a function h is hard to approximate for $$\\textsf{AC}^0$$ AC 0 circuits, one method is to (a) design some distribution over random restrictions or random projections, (b) show that $$\\textsf{AC}^0$$ AC 0 circuits simplify to shallow decision trees under these restrictions/projections, and finally (c) show that after applying the restriction/projection, h is hard to approximate for shallow decision trees with respect to an appropriate distribution. We show that (roughly speaking) if h can be proven to be hard to approximate by a proof with that structure, then XORing multiple copies of h amplifies its hardness. We apply our technique to two well-known average-case hardness results: the average-case depth hierarchy theorem (Håstad et al., 2017) and the inapproximability of the majority function. Our analysis involves a new kind of XOR lemma for decision trees, which might be of independent interest.