In this paper we give new extremal bounds on polynomial threshold function (PTF) representations of Boolean functions. Our results include the following:

\bulletAlmost every Boolean function has PTF degree at most \frac{n}{2} + (\sqrt {\text{n log n)}} . Together with results of Anthony and Alon, this establishes a conjecture of Wang and Williams [26] and Aspnes, Beigel, Furst, and Rudich [3] up to lower order terms.

\bulletEvery Boolean function has PTF density at most ( - 1\frac{1} {{o(n)}})2_{}^n This improves a result of Gotsman [12].

\bulletEvery Boolean function has weak PTF density at most o\left( \text{1} \right)2_{}^n . This gives a negative answer to a question posed by Saks [23].

\bulletPTF degree \left\lfloor {\log _2^{} m} \right\rfloor + 1 is necessary and sufficient for Boolean functions with sparsity m. This answers a question of Beigel [5].