The central result is a negative one for two exact calculations. For every fixed rational p in the paper's stated interval, maximizing an Lp norm over a generator-represented zonotope is W[1]-hard when dimension is the parameter, with a running-time lower bound conditional on ETH. The corresponding Two-Layer ICNN Lp-Lipschitz Constant problem is also W[1]-hard with respect to input dimension and has the stated ETH-conditional lower bound.
The calculation behind the claim
At the heart of the work is a threshold question about a generator-represented zonotope: does the maximum Lp norm of its points, generated by a rational matrix, reach a rational threshold?
For conjugate exponent pairs, the paper establishes an equivalence between the Two-Layer input-convex neural network, or ICNN, Lp-Lipschitz Constant problem and Lq norm maximization over zonotopes.
A graph problem supplies the hard instances
The reductions start from Multicolored Clique instances and construct a generator matrix with one generator per node, one per edge and one extra generator.
An explicit Euclidean-norm reduction proves W[1]-hardness in dimension d = 2k + 1. It also derives the stated ETH contradiction for algorithms with running time ρ(d)N^{o(d)}.
A second reduction uses the support function of a centrally symmetric zonotope and works in dimension 2k rather than 2k + 1. Its interpolation proposition computes rational generators and a positive rational delta in polynomial time for prescribed support-function values.
Extending the result to fixed Lp norms
To handle fixed rational p, a gap-transfer proposition starts from a rational gap instance A in dimension d and constructs a rational matrix B in dimension 2d with positive thresholds.
The threshold is required to be rational, so the paper chooses a rational threshold between the relevant p-th roots. This transfers the gap from p-th-power norm maximization to ordinary Lp norm maximization.
For every fixed rational p in the stated interval, p-th-power norm maximization over zonotopes is W[1]-hard with the paper's ETH-conditional running-time lower bound. Ordinary Lp norm maximization over zonotopes has the same parameterized hardness and lower bound.
A matching barrier for the network problem
The Two-Layer ICNN Lp-Lipschitz Constant problem has the same form of barrier: for every fixed rational p in the stated interval, it is W[1]-hard with respect to input dimension and has the stated ETH-conditional running-time lower bound.
The authors say the ETH-based running-time bounds make brute-force enumeration of zonotope vertices or neural-network linear regions essentially optimal.
Scope and status
The hardness statements are restricted to fixed rational exponents in the paper's stated interval, rational generator-matrix representations of zonotopes, and the specified two-layer ICNN architecture.
The running-time lower bounds are conditional on ETH, and the paper leaves open whether the problems are contained in W[1].
The document is an arXiv preprint, version 1, dated 25 Aug 2026. It also reports several independent concurrent papers resolving the same problem.
The authors report that initial versions of both reductions were independently found using LLMs in May 2026, with all authors joining forces in July 2026.
Paper data and sources
Original title: Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes
Authors: Aritra Das, Vincent Froese, Moritz Grillo et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text