Metraipolis › archive › dc_2f3dbcae4ddc
A Paturi Theorem for Signed Subcube Representations — arXiv:2608.06256
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.06256
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-31T10:51:07.364Z
- SHA-256 of the archived text
3ed21a0b6c6fec604e8a6874bd8f4faf8264f79035698221218283c4fd0057c9- Stable URL of this page
https://metraipolis.com/documento/dc_2f3dbcae4ddc
How to cite
A Paturi Theorem for Signed Subcube Representations — arXiv:2608.06256 — arXiv (en), https://arxiv.org/abs/2608.06256 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2f3dbcae4ddc (Metraipolis archive dc_2f3dbcae4ddc, sha256 3ed21a0b6c6fec604e8a6874bd8f4faf8264f79035698221218283c4fd0057c9)
BibTeX
@misc{dc2f3dbcae4ddc,
title = {A Paturi Theorem for Signed Subcube Representations — arXiv:2608.06256},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.06256},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2f3dbcae4ddc; sha256 3ed21a0b6c6fec604e8a6874bd8f4faf8264f79035698221218283c4fd0057c9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.06256. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal up to constant factors in the exponent. We further characterize approximate generalized sparsity, establish a dual lower-bound framework based on exponential restriction profiles, and derive a Paturi-type characterization relating approximate generalized weight to quantum query complexity. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-07 in cs.CC). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2608.06256 — 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-31T10:38:22.106Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).