The threshold degree of a Boolean function f is the minimum degree of a real polynomial p that represents f in sign: f(x)sgnp(x). In a seminal 1969 monograph, Minsky and Papert constructed a polynomial-size constant-depth -circuit in n variables with threshold degree (n13) This bound underlies some of today's strongest results on constant-depth circuits. It has been an open problem (O'Donnell and Servedio, STOC 2003) to improve Minsky and Papert's bound to n(1)+13

We give a detailed solution to this problem. For any fixed k1 we construct an -formula of size n and depth k with threshold degree (nk−12k−1). This lowerbound nearly matches a known O(n) bound for arbitrary formulas, and is exactly tight for regular formulas. Our result proves a conjecture due to O'Donnell and Servedio (STOC 2003) and a different conjecture due to Bun and Thaler (2013). Applications to communication complexity and computational learning are given