Abstract:The approximate non-deterministic degree of a Boolean function $f$, denoted $\mathsf{ndeg}_\epsilon(f)$ (written $\mathsf{N}_\epsilon(f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0 \le |p(x)| \le \epsilon$ 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 resolved by Kothari, Kovacs-Deak, Wang, and Yang, who showed that for every total Boolean function $f$, \[ deg(f) \le \widetilde O\!\left(\operatorname{rdeg}(f)^3\right). \]
In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by $\mathsf{N}_\epsilon(f)$ and $\mathsf{N}_\epsilon(\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<\epsilon<1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_{\epsilon}(f), \mathsf N_{\epsilon}(\overline f)). \]
This conjecture, if true, would imply a polynomial version of the rational degree result and bring us closer to resolving de Wolf's longstanding non-deterministic degree conjecture.
In this work, we make the first systematic progress on this problem, establishing the conjecture for several broad and natural function classes: monotone and unate functions, functions of bounded alternation number, symmetric functions, $k$-uniform hypergraph properties, and read-$k$ Disjunctive Normal Form (DNF) formulas.
| Comments: | 21 pages |
| Subjects: | Computational Complexity (cs.CC); Quantum Physics (quant-ph) |
| Cite as: | arXiv:2605.23336 [cs.CC] |
| (or arXiv:2605.23336v1 [cs.CC] for this version) | |
| https://doi.org/10.48550/arXiv.2605.23336 arXiv-issued DOI via DataCite (pending registration) |
From: Samruddhi Suresh Pednekar [view email]
[v1]
Fri, 22 May 2026 07:52:09 UTC (31 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。