Near-optimal lower bounds on the threshold degree and sign-rank of AC 0

The threshold degree of a Boolean function f ∶{0,1} n →{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) F ij . Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits (AC 0 ) 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 0 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 0 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 0 , strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of AC 0 .

Authors

• Alexander A. Sherstov
• Pei Wu

Keywords

• communication complexity
• constant-depth circuits
• sign-rank
• sign-representation by polynomials
• threshold degree
• unbounded-error communication