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

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.