Almost every Boolean function has central threshold degree
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(-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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.15057
curl -X POST /api/v1/records/arxiv/2610.15057/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.15057/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'