Theory of Computing Seminar

The threshold degree of a Boolean function f is the minimum
degree of a real polynomial p that represents f in sign:
f(x)=sgn p(x).  In a seminal 1969 monograph, Minsky and Papert
constructed a polynomial-size constant-depth AND/OR circuit
in n variables with threshold degree Omega(n^{1/3}). This bound
underlies the fastest known algorithms for constant-depth
circuits. It has been an open problem (O'Donnell and Servedio,
STOC 2003) to improve Minsky and Papert's bound to n^{Omega(1)+1/3}.

We give a detailed solution to this problem. For any k>=1, we
construct an AND/OR formula of size n and depth k with threshold
degree Omega(n^{(k-1)/(2k-1)}).  This lower bound nearly matches
the famous O(sqrt(n)) bound for arbitrary formulas (Ambainis,
Childs, Reichardt, Spalek, Zhang, FOCS 2007).  Our result
proves a conjecture due to O'Donnell and Servedio (STOC 2003)
and a different conjecture due to Bun and Thaler (2013).