The threshold degree of a Boolean function $f$ is the minimum degree of
a real polynomial $p$ that represents $f$ in sign: $f(x)\equiv\mathrm{sgn}\; p(x)$. In a seminal 1969
monograph, Minsky and Papert constructed a polynomial-size constant-depth
$\{\wedge,\vee\}$-circuit in $n$ variables with threshold degree $\Omega(n^{1/3}).$ 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^{\Omega(1)+1/3}.$

We give a detailed solution to this problem. For any fixed $k\geq1,$ we construct
an $\{\wedge,\vee\}$-formula of size $n$ and depth $k$ with threshold degree $\Omega(n^{\frac{k-1}{2k-1}})$. This lower
bound nearly matches a known $O(\sqrt{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.