On the Approximate Non-Deterministic Degree of Total Boolean Functions

Abstract

The approximate non-deterministic degree of a Boolean function $f$, denoted ${\mathsf{ndeg}}_{\hat{I}}\mu (f)$ (written ${\mathsf{N}}_{\hat{I}}\mu (f)$ for brevity), is the minimum degree of a real polynomial $p$ such that $0\le |p(x)|\le \hat{I}\mu$ 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}}_{\hat{I}}\mu (f)$ and ${\mathsf{N}}_{\hat{I}}\mu (\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<\hat{I}\mu <1$, \[ \widetilde{deg}(f) \le \operatorname{poly}(\mathsf N_ε(f), \mathsf N_ε(\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.

21 pages