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). Introduced
in the seminal work of Minsky and Papert (1969), this notion is central to
some of the strongest algorithmic and complexity-theoretic results for
constant-depth circuits. One problem that has remained open for several
decades, with applications to computational learning and communication
complexity, is to determine the maximum threshold degree of a polynomial-size
constant-depth circuit in n variables. The best lower bound prior to our
work was Omega(n^{(d-1)/(2d-1)}) for circuits of depth d. We obtain a polynomial
improvement for every depth d, with a lower bound of Omega(n^{3/7}) for depth 3
and Omega(sqrt{n}) for depth d>=4. The proof contributes an approximation-theoretic
technique of independent interest, which exploits asymmetry in circuits to
prove their hardness for polynomials.