Metraipolis › archive › dc_04fc9049006a

Parity Decision Trees of Depth $O(4^d \log\|\widehat f\|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$ — arXiv:2611.03452

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03452
License (as archived)
CC0-1.0
Archived
2026-11-03T11:46:33.001Z
SHA-256 of the archived text
ccd25d0a6d9f0c481407327bd1da73bb149d6626944b30e574e0523c6484274a
Stable URL of this page
https://metraipolis.com/documento/dc_04fc9049006a

How to cite

Parity Decision Trees of Depth $O(4^d \log\|\widehat f\|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$ — arXiv:2611.03452 — arXiv (en), https://arxiv.org/abs/2611.03452 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_04fc9049006a (Metraipolis archive dc_04fc9049006a, sha256 ccd25d0a6d9f0c481407327bd1da73bb149d6626944b30e574e0523c6484274a)
BibTeX
@misc{dc04fc9049006a,
  title = {Parity Decision Trees of Depth $O(4^d log|widehat f|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$ — arXiv:2611.03452},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03452},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_04fc9049006a; sha256 ccd25d0a6d9f0c481407327bd1da73bb149d6626944b30e574e0523c6484274a},
  year = {2026}
}

Archived text

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

Let $f\colon F_2^n\to\{-1,+1\}$ have $F_2$-degree $d\ge2$. We prove that its deterministic parity decision tree depth satisfies \[ D_{\oplus} (f)= O(4^d \log_2\|\widehat f\|_1) = O(4^d \log_2 s(f)), \] where $\|\widehat f\|_1=\sum_\xi|\widehat f(\xi)|$ is the Fourier spectral norm and $s(f)$ is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on $d$. This improves the previously best known bound of $O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)$ due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for $\mathrm{XOR}$ functions of $F_2$-degree $O(\log\log s(f))$, extending the previously accessible range $d=O(1)$. The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to $F_2$ to lower the degree on every coset of a common subspace.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.03452 — 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-11-03T11:08:22.227Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).