Extremal Properties of Polynomial Threshold Functions.
R. O'Donnell and R. Servedio.
Journal of Computer and System Sciences , 74(3), 2008, pp. 298-312 (special issue for CCC 2003).
Preliminary version appeared in Eighteenth Annual Conference on Computational Complexity (CCC), 2003, pp. 3-12.
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}.

pdf of conference version

pdf of journal version

Back to main papers page