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 i j ] as the minimum rank of a real matrix M with sgn M i j = ( − 1 ) F i j . 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,"> 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 .