On the Approximate Non-Deterministic Degree of Total Boolean Functions

Samruddhi Pednekar Supartha Podder Stony Brook University, New York, USA {spednekar, supartha}@cs.stonybrook.edu · 2026

Read On the Approximate Non-Deterministic Degree of Total Boolean Functions by Samruddhi Pednekar Supartha Podder Stony Brook University, New York, USA {spednekar, supartha}@cs.stonybrook.edu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-23336.txt.

Introduction

Pednekar and Podder advance a decades-old question about how hard Boolean functions are to approximate with polynomials. They study approximate non-deterministic degree, which forces a polynomial near zero on false inputs and at least one on true inputs. A recent result bounded exact degree by a cube of rational degree, and its authors conjectured a stronger polynomial bound from this new measure. Pednekar and Podder prove that conjecture for monotone and unate functions, bounded-alternation functions, symmetric functions, uniform hypergraph properties, and read-k DNF formulas.

Catalog record

CREATORSamruddhi Pednekar Supartha Podder Stony Brook University, New York, USA {spednekar, supartha}@cs.stonybrook.edu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76678
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.23336

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Approximate Non-Deterministic Degree of Total Boolean Functions Samruddhi Pednekar Supartha Podder Stony Brook University, New York, USA {spednekar, supartha}@cs.stonybrook.edu Abstract The approximate non-deterministic degree of a Boolean function f f , denoted 𝗇𝖽𝖾𝗀 ϵ ​ ( f ) \mathsf{ndeg}_{\epsilon}(f) (written 𝖭 ϵ ​ ( f ) \mathsf{N}_{\epsilon}(f) for brevity), is the minimum degree of a real polynomial p p such that 0 ≤ | p ⁡ ( x ) | ≤ ϵ 0\leq|p(x)|\leq\epsilon whenever f ⁡ ( x ) = 0 f(x)=0 , and | p ⁡ ( x ) | ≥ 1 |p(x)|\geq 1 whenever f ⁡ ( x ) = 1 f(x)=1 . Unlike exact non-deterministic degree, which only requires the polynomial to be nonzero on 1 1 -inputs, this measure enforces a uniform gap: the polynomial must stay close to zero on all 0 0 -inputs and bounded away from zero on all 1 1 -inputs. The rational degree conjecture, open for over three decades, was recently resolved by Kothari, Kovacs-Deak, Wang, and Yang [ 24 ] , who showed that for every total Boolean function f f , deg ⁡ ( f ) ≤ O ~ ​ ( rdeg ⁡ ( f ) 3 ) . \deg(f)\leq\widetilde{O}\!\left(\operatorname{rdeg}(f)^{3}\right). In their paper, they explicitly propose a stronger conjecture: that approximate degree is polynomially bounded by 𝖭 ϵ ​ ( f ) \mathsf{N}_{\epsilon}(f) and 𝖭 ϵ ​ ( f ¯ ) \mathsf{N}_{\epsilon}(\overline{f}) jointly, i.e., for every total Boolean function f f and every constant 0 < ϵ < 1 0<\epsilon<1 , deg ~ ​ ( f ) ≤ poly ⁡ ( 𝖭 ϵ ​ ( f ) , 𝖭 ϵ ​ ( f ¯ ) ) . \widetilde{\deg}(f)\leq\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 [ 16 ] . 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 k -uniform hypergraph properties, and read- k k Disjunctive Normal Form (DNF) formulas. 1 Introduction A central goal in the analysis of Boolean functions is to understand how different complexity measures relate to one another. Many of these measures come from very different models: decision trees, certificates, block sensitivity, quantum query algorithms, and real polynomial representations. Nevertheless, for total Boolean functions, many of them are known to be polynomially related. The foundational work of Nisan and Szegedy [ 30 ] showed that the degree and approximate degree of a Boolean function are polynomially related to several standard complexity measures, including block sensitivity, certificate complexity, and deterministic query complexity. This circle of equivalences was later extended to other measures, and one of the main remaining gaps, the sensitivity conjecture, was resolved by Huang [ 20 ] . Another major open problem from the same line of work concerned rational representations of Boolean functions. This question, attributed to Fortnow and recorded by Nisan and Szegedy [ 30 ] , asked whether rational degree is polynomially related to ordinary degree. The rational degree of a Boolean function f:\{0,1\}^{n}\to\{0,1\} , denoted \operatorname{rdeg}(f) , is the least degree needed to represent f exactly on the Boolean cube as a quotient p/q of real polynomials, where q is nonzero on every input. Since every polynomial representation is also a rational representation with denominator 1 , we always have \operatorname{rdeg}(f)\leq\deg(f). The rational degree conjecture asked for a converse up to polynomial loss: does there exist a constant c such that \deg(f)\leq O(\operatorname{rdeg}(f)^{c}) for every total Boolean function f ? This conjecture remained open for more than three decades. It was recently proved by Kothari, Kovacs-Deak, Wang, and Yang [ 24 ] , who showed that, for every total Boolean function f , \deg(f)\leq\widetilde{O}\!\left(\operatorname{rdeg}(f)^{3}\right). Thus rational degree also belongs to the family of Boolean function measures that are polynomially related for total functions [ 24 ] . The restriction to total functions is important: for partial functions, the analogous statement is false, as shown by Iyer et al. [ 21 ] . A key reason rational degree is natural is its close connection to nondeterminism. A non-deterministic polynomial for f is a real polynomial p such that p(x)\neq 0\quad\Longleftrightarrow\quad f(x)=1\qquad\text{for all }x\in\{0,1\}^{n}. The non-deterministic degree of f , denoted \operatorname{ndeg}(f) , is the minimum degree of such a polynomial. Rational degree can be described exactly in terms of non-deterministic degree: \operatorname{rdeg}(f)=\max\{\operatorname{ndeg}(f),\operatorname{ndeg}(\overline{f})\}. In other words, rational degree measures the larger of the two non-deterministic degrees associated with f and its complement. This connection also brings quantum query complexity into the picture. de Wolf showed that non-deterministic degree is equal, up to constant factors, to non-deterministic quantum query complexity [ 16 ] . Motivated by the classical relation D(f)\leq C^{(0)}(f)C^{(1)}(f), or equivalently by the product of non-deterministic query complexities for f and \overline{f} , de Wolf conjectured that Conjecture 1 ( [ 16 ] ) . For every total Boolean function f , D(f)\leq O\!\left(\operatorname{ndeg}(f)\operatorname{ndeg}(\overline{f})\right) The dependence on both f and \overline{f} is necessary: for example, \operatorname{OR}_{n} has very small non-deterministic degree, while its deterministic query complexity is large, and the same obstruction appears for \operatorname{AND}_{n} after taking complements. de Wolf’s conjecture is stronger than the rational degree conjecture. Indeed, since \operatorname{rdeg}(f)=\max\{\operatorname{ndeg}(f),\operatorname{ndeg}(\overline{f})\} , the conjecture would imply a quadratic upper bound of ordinary degree in terms of rational degree. Moreover, since \operatorname{ndeg}(f)\leq\deg(f) and \operatorname{ndeg}(\overline{f})\leq\deg(\overline{f}) and \deg(f)=\deg(\overline{f}) , the conjecture would also give D(f)\leq O(\deg(f)^{2}) . [ 24 ] gave a weaker polynomial form. In particular, they show D(f)\leq O\!\left(\operatorname{ndeg}(f)^{2}\operatorname{ndeg}(\overline{f})^{2}\right),\quad\textit{and \hskip 10.22217pt}D(f)\leq O\!\left(\operatorname{ndeg}(f)^{1.5}\operatorname{ndeg}(\overline{f})^{1.5}\log n\right), but the original product conjecture remains open [ 24 ] . 1.1 Approximate version of non-deterministic degree [ 16 , 24 ] proposed an even stronger version of Conjecture 1 involving approximate non-deterministic degree: For any constant 0<\epsilon<1 define the \epsilon -approximate non-deterministic degree of f , denoted 1 1 1 Prior work [ 16 , 24 ] denotes \epsilon -approximate non-deterministic degree of f as \operatorname{ndeg}_{\epsilon}(f) . We denote this as \mathsf{N}_{\epsilon}(f) for easy readability. We also used \mathsf{N}(f) for \mathsf{N}_{\epsilon}(f) where \epsilon=1/3 . These should not be confused with the notation \mathsf{N}_{q}(f) or \mathsf{N}_{c}(f) used in [ 16 ] for denoting non-deterministic classical query complexity and non-deterministic classical communication complexity respectively, which we do not discuss here. \mathsf{N}_{\epsilon}(f) , to be the minimum degree of a real polynomial p such that |p(x)|\leq\epsilon\quad\text{whenever }f(x)=0,\qquad|p(x)|\geq 1\quad\text{whenever }f(x)=1. When \epsilon=0 , this recovers the exact non-deterministic degree, denoted by \operatorname{ndeg}(f) . For positive \epsilon , however, the measure becomes more delicate. Exact non-deterministic degree only requires the polynomial \deg(f) \widetilde{\deg}(f) \operatorname{rdeg}(f)=\max\{\operatorname{ndeg}(f),\operatorname{ndeg}(\overline{f})\} \operatorname{ndeg}(f) odeg_{\epsilon}(f)=\Theta(\operatorname{ndeg}\epsilon(f)) \widetilde{\operatorname{rdeg}}(f) Figure 1: Relations between different degrees for total Boolean functions. A\rightarrow B denotes A\leq B . to be nonzero on 1 inputs. Approximate non-deterministic degree asks for a uniform gap: the polynomial must be small on all 0 inputs and bounded away from zero on all 1 inputs. Thus it is a one-sided bounded version of non-deterministic degree. This notion is closely related, up to changes in constants, to one-sided approximate degree, which has been studied for example in [ 36 , 10 ] . The natural two-sided analogue is

Read the complete text