Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 4 min ago
PreprintarXiv licencearXiv

Almost every Boolean function has central threshold degree

  • Martin Anthony
Open at sourcePDFDOICite

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 ⌊ n/2⌋ or ⌈ n/2⌉, except with probability at most exp(−c2n/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.

Related

  1. An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
    Alexandr Valyuzhenich
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. Almost sharp sharpness for Poisson Boolean percolation
    Barbara Dembin, Vincent Tassion
    The Annals of ProbabilityPeer-reviewedCC BY-NC 4.0Full text18 citedMathematical physicsHALOpenAlex
  3. Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
    Kyle Luh
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  4. Certificate Complexity of Elementary Symmetric Boolean Functions of Arbitrary Degree
    Jing Zhang, Yuan Li
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv
  5. Sensitivity and Block Sensitivity of Elementary Symmetric Boolean Functions of Arbitrary Degree
    Yuan Li, Jing Zhang
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{anthony2026almost,
  title = {{Almost every Boolean function has central threshold degree}},
  author = {Martin Anthony},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15057},
  eprint = {2610.15057},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15057},
}
RIS
TY  - UNPB
TI  - Almost every Boolean function has central threshold degree
AU  - Martin Anthony
PY  - 2026
DA  - 2026/10/22
PB  - arXiv
DO  - 10.48550/arxiv.2610.15057
UR  - https://arxiv.org/abs/2610.15057
AB  - 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 ⌊ n/2⌋ or ⌈ n/2⌉, except with probability at most exp(−c2^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.
ER  -