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).