Almost every Boolean function has central threshold degree

Abstract

The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree either $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$, except with probability at most $\exp (-c{2}^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. The paper proves a 1991 conjecture of Aspnes, Beigel, Furst and Rudich. It also proves a 1991 conjecture of Wang and Williams for even $n$ and its main concentration assertion for odd $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.

arXiv comment12 pages. Revised abstract and exposition to clarify the conjectures resolved; references updated. Results and proofs unchanged