{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiblemo2ohy4deec4nnoc65eusl3aftee5pl6bndvxudgkzerbd72e",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmnyqe6kyji2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.23336v1",
  "publishedAt": "2026-05-25T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Samruddhi Pednekar",
    "Supartha Podder"
  ],
  "textContent": "**Authors:** Samruddhi Pednekar, Supartha Podder\n\nThe 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 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}_ε(f)$ and $\\mathsf{N}_ε(\\overline{f})$ jointly, i.e., for every total Boolean function $f$ and every constant $0<ε<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.",
  "title": "On the Approximate Non-Deterministic Degree of Total Boolean Functions"
}