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 = [F_ij] as the minimum rank of a real matrix M with sgn M_ij = (−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¹−^ϵ) and sign-rank exp(Ω(n¹−^ϵ)), 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. Our work gives some of the strongest lower bounds to date on the communication complexity of AC⁰.