{"id":"arxiv/2610.15057","url":"https://arxiv.org/abs/2610.15057","tags":["cs.DM","cs.IT","math.CO"],"score":0,"title":"Almost every Boolean function has central threshold degree","domain":"cs.DM","source":"arxiv","authors":["Martin Anthony"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-10","reactions":{}}