NEAR-OPTIMAL LOWER BOUNDS ON THE THRESHOLD DEGREE AND SIGN-RANK OF AC⁰

The threshold degree of a Boolean function f : {0, 1}ⁿ → {0, 1} is the minimum degree of a real polynomial p that represents f in sign: sgn p(x) = (-1)^f(x). A related notion is sign-rank, defined for a Boolean matrix F = [Fij] as the minimum rank of a real matrix M with sgn Mij = (-1)^Fij. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC⁰) is a well-known and extensively studied open problem with complexity-theoretic and algorithmic applications. We give an essentially optimal solution to this problem. For any ϵ > 0, we construct an AC⁰ circuit in n variables that has threshold degree Ω(n^1-ϵ) and sign-rank exp(Ω(n^1-ϵ)), improving on the previous best lower bounds of Ω(√n) and exp(Ω̃(√n)), respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of AC⁰ circuits of any given depth, with a strict improvement starting at depth 4. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of AC⁰, strictly subsuming previous work on these quantities.