Metraipolis › archive › dc_46f218fbf92d

An Optimal Separation Between Certificate Complexity and Approximate Degree — arXiv:2608.30351

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.30351
License (as archived): CC0-1.0
Archived: 2026-10-17T10:07:18.209Z
SHA-256 of the archived text: e6b8cdfddb967787ed97a83824b6c1235b448a158fa5e83f9d2addea236a08b2
Stable URL of this page: https://metraipolis.com/documento/dc_46f218fbf92d

How to cite

An Optimal Separation Between Certificate Complexity and Approximate Degree — arXiv:2608.30351 — arXiv (en), https://arxiv.org/abs/2608.30351 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_46f218fbf92d (Metraipolis archive dc_46f218fbf92d, sha256 e6b8cdfddb967787ed97a83824b6c1235b448a158fa5e83f9d2addea236a08b2)

BibTeX

@misc{dc46f218fbf92d,
  title = {An Optimal Separation Between Certificate Complexity and Approximate Degree — arXiv:2608.30351},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.30351},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_46f218fbf92d; sha256 e6b8cdfddb967787ed97a83824b6c1235b448a158fa5e83f9d2addea236a08b2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30351. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tilde{\Omega}(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function $f$ satisfies $C(f)\le O(\tilde{deg}(f)^4)$ by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation $C(f)=\tilde{\Omega}(\tilde{deg}(f)^3)$ by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate $0$-certificate complexity from unambiguous $1$-certificate complexity. It already has the required certificate hardness, but its $0$-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its $1$-condition and restrict the $0$-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function $G$ with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree $\tilde{O}(\sqrt n)$. The verifier forms a low-degree count $W$ of the candidate $1$-certificates that remain compatible with the asserted $0$-certificate, and tests whether this count is zero. Crucially, the construction ensures that $W$ never exceeds $\tilde{O}(n)$, instead of the $\Theta(n^2)$ candidate pairs it counts bringing the verification down to degree $\tilde{O}(\sqrt n)$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-01 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2608.30351 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T10:02:18.385Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).