Near-optimal lower bounds on the threshold degree and sign-rank of AC 0
Alexander A. Sherstov, Pei Wu · 2019
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=[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 (AC0) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications.