pith. sign in

arxiv: 2605.23336 · v1 · pith:35Z66ERDnew · submitted 2026-05-22 · 💻 cs.CC · quant-ph

On the Approximate Non-Deterministic Degree of Total Boolean Functions

Samruddhi Pednekar , Supartha Podder This is my paper

Pith reviewed 2026-05-25 02:49 UTC · model grok-4.3

classification 💻 cs.CC quant-ph
keywords approximate degreenon-deterministic degreeBoolean functionsmonotone functionssymmetric functionsDNF formulashypergraph propertiesunate functions
0
0 comments X

The pith

For monotone, symmetric, and other structured total Boolean functions, approximate degree is polynomially bounded by the approximate non-deterministic degrees of the function and its complement.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a polynomial relation between approximate degree and approximate non-deterministic degree for several natural classes of total Boolean functions. It establishes the bound for monotone and unate functions, functions with bounded alternation number, symmetric functions, k-uniform hypergraph properties, and read-k DNF formulas. This is shown by constructing suitable witnessing polynomials that respect the structural restrictions of each class. A reader would care because these classes cover many functions arising in complexity and learning theory, and the result gives concrete progress toward relating several degree measures without resolving the general case.

Core claim

The paper shows that for every total Boolean function f belonging to the listed classes and every constant 0 < ε < 1, the approximate degree satisfies deg̃(f) ≤ poly(N_ε(f), N_ε(¯f)), where N_ε(f) is the minimum degree of a real polynomial that is at least 1 on all 1-inputs of f and at most ε on all 0-inputs.

What carries the argument

Approximate non-deterministic degree N_ε(f), defined as the lowest degree of a polynomial p satisfying |p(x)| ≥ 1 on f(x)=1 and 0 ≤ |p(x)| ≤ ε on f(x)=0, used to bound approximate degree via class-specific polynomial constructions.

If this is right

  • The rational degree conjecture holds for all functions in the covered classes.
  • A polynomial relation between approximate degree and non-deterministic degree is obtained for monotone, symmetric, and read-k DNF functions.
  • The non-deterministic degree conjecture receives partial progress on these structured families.
  • The same polynomial bound applies simultaneously to f and its complement for each class.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same technique might extend to additional classes defined by local structural restrictions, such as decision trees of bounded depth.
  • If the witnessing polynomials can be made explicit, they could yield new approximation algorithms or learning results for these function families.
  • The result suggests that any counterexample to the general conjecture, if it exists, must lie outside all the listed classes.

Load-bearing premise

The listed structural properties of each function class suffice to build or bound the required low-degree witnessing polynomials.

What would settle it

Exhibit one function in one of the classes (for example a monotone function or a read-k DNF) where approximate degree grows faster than every polynomial of N_ε(f) and N_ε(¯f) for some fixed ε.

Figures

Figures reproduced from arXiv: 2605.23336 by Samruddhi Pednekar, Supartha Podder.

Figure 1
Figure 1. Figure 1: Relations between different de￾grees for total Boolean functions. A → B denotes A ≤ 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 appr… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for every total Boolean function f in the classes of monotone and unate functions, functions of bounded alternation number, symmetric functions, k-uniform hypergraph properties, and read-k DNF formulas, and for every constant 0 < ε < 1, the approximate degree satisfies deg̃(f) ≤ poly(N_ε(f), N_ε(¯f)). The proofs rely on constructing or bounding witnessing polynomials directly from the structural properties defining each class.

Significance. If the results hold, this constitutes the first systematic verification of the stronger conjecture proposed by Kothari et al. following their resolution of the rational degree conjecture. The approach is notable for using only the structural definitions of the listed classes (monotonicity, symmetry, read-k property, etc.) to obtain the polynomial bound without parameter fitting or reduction to the general case, providing concrete, falsifiable progress toward de Wolf's non-deterministic degree conjecture.

minor comments (2)
  1. [Abstract] Abstract: the notation switches between ndeg_ε(f) and N_ε(f) without an explicit statement that the latter is an abbreviation; a single consistent symbol would improve readability.
  2. The manuscript would benefit from a brief table or paragraph summarizing which structural property is used for each class to obtain the witnessing polynomial.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. No major comments appear in the report, so we have no specific points requiring rebuttal or clarification at this time. We will address any minor editorial suggestions during the revision process.

Circularity Check

0 steps flagged

No circularity; proofs rely on class-specific structural constructions

full rationale

The paper proves the claimed polynomial bound on approximate degree for the listed function classes (monotone/unate, bounded alternation, symmetric, k-uniform hypergraph properties, read-k DNF) by directly using the structural definitions of each class to construct or bound witnessing polynomials. No derivation step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation chain. The rational degree result is cited from external prior work (Kothari et al.), and the new results are presented as independent progress on the stronger conjecture for restricted classes. The derivation chain is self-contained against the structural assumptions and does not invoke the general conjecture.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Abstract-only review reveals no free parameters, invented entities, or non-standard axioms; all content rests on standard definitions of polynomial degree and Boolean function classes from prior literature.

axioms (1)
  • standard math Real polynomials can be used to approximate Boolean functions with the stated sign and magnitude conditions
    Invoked in the definition of N_ε(f) and approximate degree.

pith-pipeline@v0.9.0 · 5900 in / 1278 out tokens · 62543 ms · 2026-05-25T02:49:59.360620+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages · 2 internal anchors

  1. [1]

    2023 , eprint=

    On the Rational Degree of Boolean Functions and Applications , author=. 2023 , eprint=

    work page 2023

  2. [2]

    43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) , pages =

    Chugh, Rahul and Podder, Supartha and Sanyal, Swagato , title =. 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023) , pages =. 2023 , volume =. doi:10.4230/LIPIcs.FSTTCS.2023.27 , annote =

    work page doi:10.4230/lipics.fsttcs.2023.27 2023

  3. [3]

    2014 , eprint=

    Learning circuits with few negations , author=. 2014 , eprint=

    work page 2014

  4. [4]

    , author=

    Symmetric Boolean functions. , author=

    work page

  5. [5]

    , author=

    On the degree of Polynomials that approximate symmetric boolean functions. , author=

    work page

  6. [6]

    Proceedings of the 15th Annual

    Ronald de Wolf , title =. Proceedings of the 15th Annual. 2000 , url =. doi:10.1109/CCC.2000.856758 , timestamp =

    work page doi:10.1109/ccc.2000.856758 2000

  7. [7]

    On the Degree of Boolean Functions as Real Polynomials , volume =

    Nisan, Noam and Szegedy, Mario , year =. On the Degree of Boolean Functions as Real Polynomials , volume =. Computational Complexity , doi =

    work page

  8. [8]

    Complexity measures and decision tree complexity: A survey , volume =

    Buhrman, Harry and de Wolf, Ronald , year =. Complexity measures and decision tree complexity: A survey , volume =. Theoretical Computer Science , doi =

    work page

  9. [9]

    Schwartz, J. T. , title =. 1980 , issue_date =. doi:10.1145/322217.322225 , journal =

    work page doi:10.1145/322217.322225 1980

  10. [10]

    2013 , isbn =

    Tal, Avishay , title =. 2013 , isbn =. doi:10.1145/2422436.2422485 , booktitle =

    work page doi:10.1145/2422436.2422485 2013

  11. [11]

    46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) , pages =

    Chaubal, Siddhesh and G\'. 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.MFCS.2021.31 , annote =

    work page doi:10.4230/lipics.mfcs.2021.31 2021

  12. [12]

    Alternation, sparsity and sensitivity: Bounds and exponential gaps , volume=

    Dinesh, Krishnamoorthy and Sarma, Jayalal , year=. Alternation, sparsity and sensitivity: Bounds and exponential gaps , volume=. doi:10.1016/j.tcs.2018.11.015 , journal=

    work page doi:10.1016/j.tcs.2018.11.015 2018

  13. [13]

    44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages =

    Lin, Chengyu and Zhang, Shengyu , title =. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.ICALP.2017.51 , annote =

    work page doi:10.4230/lipics.icalp.2017.51 2017

  14. [14]

    2021 , eprint=

    Analysis of Boolean Functions , author=. 2021 , eprint=

    work page 2021

  15. [15]

    2022 , eprint=

    Query complexity of Boolean functions on slices , author=. 2022 , eprint=

    work page 2022

  16. [16]

    Algorithmic Polynomials

    Alexander A. Sherstov , title =. CoRR , volume =. 2018 , url =. 1801.04607 , timestamp =

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  17. [17]

    , title =

    Sherstov, Alexander A. , title =. Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity , pages =. 2008 , isbn =. doi:10.1109/CCC.2008.18 , abstract =

    work page doi:10.1109/ccc.2008.18 2008

  18. [18]

    2014 , eprint=

    Hardness Amplification and the Approximate Degree of Constant-Depth Circuits , author=. 2014 , eprint=

    work page 2014

  19. [19]

    2026 , eprint=

    Rational degree is polynomially related to degree , author=. 2026 , eprint=

    work page 2026

  20. [20]

    Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =

    Paturi, Ramamohan , title =. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =. 1992 , isbn =. doi:10.1145/129712.129758 , abstract =

    work page doi:10.1145/129712.129758 1992

  21. [21]

    , title =

    Sherstov, Alexander A. , title =. 2014 , isbn =. doi:10.1145/2591796.2591871 , booktitle =

    work page doi:10.1145/2591796.2591871 2014

  22. [22]

    Bun, Mark and Thaler, Justin , title =. Found. Trends Theor. Comput. Sci. , month = dec, pages =. 2022 , issue_date =. doi:10.1561/0400000107 , abstract =

    work page doi:10.1561/0400000107 2022

  23. [23]

    SIAM Journal on Computing , volume=

    The intersection of two halfspaces has high threshold degree , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    work page 2013

  24. [24]

    41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , year=

    On the sensitivity conjecture for read-k formulas , author=. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) , year=

    work page 2016

  25. [25]

    Classification by polynomial surfaces , journal =

    Martin Anthony , abstract =. Classification by polynomial surfaces , journal =. 1995 , issn =. doi:https://doi.org/10.1016/0166-218X(94)00008-2 , url =

    work page doi:10.1016/0166-218x(94)00008-2 1995

  26. [26]

    , editor=

    Saks, Michael E. , editor=. Slicing the hypercube , booktitle=. 1993 , pages=

    work page 1993

  27. [27]

    Annals of Mathematics , volume=

    Induced subgraphs of hypercubes and a proof of the sensitivity conjecture , author=. Annals of Mathematics , volume=. 2019 , publisher=

    work page 2019

  28. [28]

    36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , pages=

    On the Sensitivity Conjecture for Disjunctive Normal Forms , author=. 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , pages=

    work page

  29. [29]

    Theoretical Computer Science , volume=

    On recognizing graph properties from adjacency matrices , author=. Theoretical Computer Science , volume=. 1976 , publisher=

    work page 1976

  30. [30]

    computational complexity , volume=

    On the fine-grained query complexity of symmetric functions , author=. computational complexity , volume=. 2025 , publisher=

    work page 2025

  31. [31]

    Combinatorica , volume=

    A topological approach to evasiveness , author=. Combinatorica , volume=. 1984 , publisher=

    work page 1984

  32. [32]

    33rd Symposium on Theoretical Aspects of Computer Science , year=

    Quantum Query Complexity of Subgraph Isomorphism and Homomorphism , author=. 33rd Symposium on Theoretical Aspects of Computer Science , year=

    work page

  33. [33]

    Theoretical Computer Science , volume=

    Any monotone property of 3-uniform hypergraphs is weakly evasive , author=. Theoretical Computer Science , volume=. 2015 , publisher=

    work page 2015

  34. [34]

    SIAM Journal on Computing , volume=

    Symmetries, graph properties, and quantum speedups , author=. SIAM Journal on Computing , volume=. 2024 , publisher=

    work page 2024

  35. [35]

    Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science , pages=

    Monotone properties of k-uniform hypergraphs are weakly evasive , author=. Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science , pages=

    work page 2015

  36. [36]

    Leibniz International Proceedings in Informatics , year=

    Graph properties in node-query setting: effect of breaking symmetry , author=. Leibniz International Proceedings in Informatics , year=

    work page

  37. [37]

    ACM Transactions on Computation Theory (TOCT) , volume=

    On the sensitivity complexity of k-uniform hypergraph properties , author=. ACM Transactions on Computation Theory (TOCT) , volume=. 2021 , publisher=

    work page 2021

  38. [38]

    Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , pages=

    On the degree of polynomials that approximate symmetric boolean functions (preliminary version) , author=. Proceedings of the twenty-fourth annual ACM symposium on Theory of computing , pages=

    work page

  39. [39]

    approximate degree and quantum implications of Huang’s sensitivity theorem , author=

    Degree vs. approximate degree and quantum implications of Huang’s sensitivity theorem , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

    work page

  40. [40]

    SIAM Journal on Computing , volume=

    Quantum query complexity of minor-closed graph properties , author=. SIAM Journal on Computing , volume=. 2012 , publisher=

    work page 2012

  41. [41]

    ACM Transactions on Quantum Computing , volume=

    A quantum algorithm for the sub-graph isomorphism problem , author=. ACM Transactions on Quantum Computing , volume=. 2023 , publisher=

    work page 2023

  42. [42]

    Graphs and Combinatorics , volume=

    Hypergraphs with high chromatic number , author=. Graphs and Combinatorics , volume=. 1985 , publisher=

    work page 1985

  43. [43]

    International Colloquium on Automata, Languages, and Programming , pages=

    Improved lower bounds on the randomized complexity of graph properties , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2001 , organization=

    work page 2001

  44. [44]

    Acta Cybernetica , volume=

    On the randomized complexity of monotone graph properties , author=. Acta Cybernetica , volume=. 1992 , publisher=

    work page 1992

  45. [45]

    Combinatorica , volume=

    An Ω (n 4/3) lower bound on the randomized complexity of graph properties , author=. Combinatorica , volume=. 1991 , publisher=

    work page 1991

  46. [46]

    Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

    Lower bounds on the complexity of graph properties , author=. Proceedings of the twentieth annual ACM symposium on Theory of computing , pages=

    work page

  47. [47]

    28th Annual Symposium on Foundations of Computer Science (

    Lower bounds to randomized algorithms for graph properties , author=. 28th Annual Symposium on Foundations of Computer Science (. 1987 , organization=

    work page 1987

  48. [48]

    Learning circuits with few negations

    Learning circuits with few negations , author=. arXiv preprint arXiv:1410.8420 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  49. [49]

    Theory of Computing , volume=

    Testing k -monotonicity: The rise and fall of boolean functions , author=. Theory of Computing , volume=. 2019 , publisher=

    work page 2019

  50. [50]

    Theoretical Computer Science , volume=

    Alternation, sparsity and sensitivity: Bounds and exponential gaps , author=. Theoretical Computer Science , volume=. 2019 , publisher=

    work page 2019

  51. [51]

    , title =

    Nisan, N. , title =. 1989 , isbn =. doi:10.1145/73007.73038 , booktitle =

    work page doi:10.1145/73007.73038 1989

  52. [52]

    SIAM Journal on Computing , volume =

    Nisan, Noam , title =. SIAM Journal on Computing , volume =. 1991 , doi =. https://doi.org/10.1137/0220062 , abstract =

    work page doi:10.1137/0220062 1991

  53. [53]

    Combinatorica , volume=

    Polynomials with two values , author=. Combinatorica , volume=. 1997 , publisher=

    work page 1997