{"id":"arxiv/2605.23336","url":"https://arxiv.org/abs/2605.23336","tags":["cs.CC","quant-ph"],"score":0,"title":"On the Approximate Non-Deterministic Degree of Total Boolean Functions","domain":"cs.CC","source":"arxiv","authors":["Samruddhi Pednekar","Supartha Podder"],"reviews":0,"subject":"cs.CC","summary":"The approximate non-deterministic degree of a Boolean function $f$, denoted $\\mathsf{ndeg}_ε(f)$ (written $\\mathsf{N}_ε(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \\le |p(x)| \\le ε$ whenever $f(x) = 0$, and $|p(x)| \\ge 1$ whenever $f(x) = 1$. Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on $1$-inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all $0$-inputs and bounded away from zero on all $1$-inputs. The rational degree conjecture, open for over three decades, was recently…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-22","reactions":{}}