# ℓp-Norm Maximization over Zonotopes Is W[1]-Hard

arXiv: https://arxiv.org/abs/2608.15847 · HTML: https://mlsanity.com/paper/2608.15847/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2026.

## Built on by (most cited first, 1 of 1)

- [Parameterized Complexity of Lp-Lipschitz Constants for Input Convex Neural Networks and Lp-Norm Maximization over Zonotopes](https://mlsanity.com/paper/2608.24865/) (2026)

## Abstract (arXiv)

We study ℓ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 nO(d)bO(d)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 ρp(d)Lo(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.