R. O'Donnell and R. Servedio.

Preliminary version appeared in

Best Paper award, CCC 2003.

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

-- Almost every Boolean function has PTF degree at most ${\frac n 2} + O(\sqrt{n \log n})$. Together with results of Anthony and Alon, this establishes a conjecture of Wang and Williams \cite{WangWilliams:91} and Aspnes, Beigel, Furst, and Rudich \cite{ABF+:94} up to lower order terms.

-- Every Boolean function has PTF density at most $(1 - \frac{1}{O(n)})2^n.$ This improves a result of Gotsman \cite{Gotsman:89}.

-- Every Boolean function has weak PTF density at most $o(1) 2^n.$ This gives a negative answer to a question posed by Saks \cite{Saks:93}.

-- PTF degree $\lfloor \log_2 m \rfloor + 1$ is necessary and sufficient for Boolean functions with sparsity $m.$ This answers a question of Beigel \cite{Beigel:00}.