Metraipolis › archive › dc_40cf7a49459b
$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard — arXiv:2608.15847
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.15847
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T00:29:36.849Z
- SHA-256 of the archived text
3eed459100550103fedb4a009f9410e5021311811a06e819226ffdc9f985d7bb- Stable URL of this page
https://metraipolis.com/documento/dc_40cf7a49459b
How to cite
$\ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard — arXiv:2608.15847 — arXiv (en), https://arxiv.org/abs/2608.15847 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_40cf7a49459b (Metraipolis archive dc_40cf7a49459b, sha256 3eed459100550103fedb4a009f9410e5021311811a06e819226ffdc9f985d7bb)
BibTeX
@misc{dc40cf7a49459b,
title = {$ell_p$-Norm Maximization over Zonotopes Is W[1]-Hard — arXiv:2608.15847},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.15847},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_40cf7a49459b; sha256 3eed459100550103fedb4a009f9410e5021311811a06e819226ffdc9f985d7bb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.15847. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study $\ell_p$-norm maximization over zonotopes given by rational generators, with input length $L$. For fixed $p=a/b>1$, the exact Turing baseline runs in $n^{O(d)}b^{O(d)}\mathrm{poly}(L)$ time, but fixed-parameter tractability in the ambient dimension $d$ was open [FGHS25]. We prove W[1]-hardness and, under the Exponential Time Hypothesis (ETH), exclude $\rho_p(d)L^{o(d)}$ time, even for $5$-sparse generators, by encoding binary CSP constraints with normalized positive cap generators. We also give a deterministic $(1-\varepsilon)$-approximation with $\varepsilon^{-(d-1)/2}$ dependence and, among algorithms with fixed-degree polynomial dependence on $L$, rule out $(1/\varepsilon)^{o(d)}$ dependence under ETH. Support-function duality transfers the results to positive-output two-layer ReLU networks.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-18 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC) ; Computational Geometry (cs.CG).
Pagina del lavoro: https://arxiv.org/abs/2608.15847 — 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-18T23:35:48.554Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-08-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).