Abstract
This talk will establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we will show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error.
We describe how this result enables progress on several problems in complexity theory. First, we establish new bounds on the \emph{discrepancy and threshold weight} of constant-depth Boolean circuits. These results immediately yield new lower bounds on the communication and circuit complexity of functions in AC^0, and demonstrate strong limitations on existing PAC learning algorithms.
Second, we prove an \tilde{Omega}(n^{1/2}) lower bound on the \emph{approximate degree} of AND-OR trees of any constant depth. This lower bound is tight up to polylogarithmic factors, and thereby nearly completes a line of work on this problem.
Joint work with Mark Bun.