{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigwvi4lcvh4m3lid4kn62xbxxew2fc57bhmfa2efuiqrm6ihnuqcq",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mmgdx63sqpm2"
  },
  "path": "/report/2026/083",
  "publishedAt": "2026-05-19T09:53:43.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "For a Boolean function $f:\\\\{0,1\\\\}^n\\to\\\\{0,1\\\\}$, the higher-order Boolean derivative $D_S f$ computes the parity of $f$ over each $S$-dimensional subcube. We prove that $D_S f\\equiv 1$ exactly when $S$ is a maximal monomial support in the algebraic normal form of $f$. This correspondence motivates the derivative certificate depth $\\Delta_\\partial(f)$, defined as the minimum degree of a nonempty maximal algebraic normal form monomial. We study the decision problem BCD: given $f$ and $k$, decide whether $\\Delta_\\partial(f)\\le k$. We show that this problem is coNP-complete for every fixed constant $k\\ge 1$, NP-complete when $k=n$, and belongs to $\\Sigma_2^{\\oplus P}$ when $k$ is part of the input; in the variable-$k$ case it is also both NP-hard and coNP-hard. These results identify the $\\exists\\forall\\oplus$ upper bound and leave $\\Sigma_2^{\\oplus P}$-completeness as an open problem.",
  "title": "TR26-083 |  Boolean Derivative Certificates and Maximal ANF Terms | \n\n\tNicholas  Smirnov"
}