For each fixed rational p∈(1,∞), given vectors v_1,…,v_m∈Q^d defining the zonotope Z=∑_i=1^m lambda_i v_i: -1≤lambda_i≤ 1, determine whether the optimization problem max_x∈ Z|x|_p is fixed-parameter tractable when parameterized by the dimension d; that is, whether it can be solved in time f(d)| I|^O(1) for some computable function f independent of the input size.

Parameterized complexity of Lp-norm maximization over zonotopes

For each fixed rational $p\in(1,\infty)$ , given vectors $v_1,\ldots,v_m\in\mathbb{Q}^d$ defining the zonotope $Z=\left\{\sum_{i=1}^m\lambda_i v_i: -1\leq\lambda_i\leq 1\right\}$ , determine whether the optimization problem $\max_{x\in Z}\|x\|_p$ is fixed-parameter tractable when parameterized by the dimension $d$ ; that is, whether it can be solved in time $f(d)\lvert I\rvert^{O(1)}$ for some computable function $f$ independent of the input size.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

$L_p$ -Lipschitz constants of two-layer input-convex neural networks
For two-layer ReLU input-convex neural networks, computing the $L_p$ -Lipschitz constant is equivalent to maximizing the dual $L_q$ norm over a zonotope, where $p,q\in(1,\infty)$ satisfy $1/p+1/q=1$ .
source: Parameterized Complexity of $L_p$-Lipschitz Constants for Input Convex Neural Networks and $L_p$-Norm Maximization over Zonotopes

References

Primary source

arXiv

Additional references

Parameterized Complexity of L_p-Lipschitz Constants for Input Convex Neural Networks and L_p-Norm Maximization over Zonotopes — arXiv

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A new preprint claims to settle the problem by proving that faster algorithms are unlikely in three or more dimensions, but the result has not been independently verified.

The problem, posed at COLT 2025, asks whether maximizing an $\ell_p$ norm over a zonotope is fixed-parameter tractable in its dimension for fixed rational $p\in(1,\infty)$ .

Known results

$\ell_\infty$ maximization is solvable in polynomial time; $\ell_1$ maximization is fixed-parameter tractable in dimension (reported in 2025).
Shenmaier (2018) proved NP-hardness and inapproximability for $p\in[1,\infty)$ .

August 26, 2026 claimed resolution

On August 26, 2026, the preprint $\ell_p$ -Norm Maximization over Zonotopes Is W[1]-Hard claimed that, for every fixed rational $p>1$ , exact maximization is $\mathrm{W}[1]$ -hard parameterized by dimension, even with $5$ -sparse generators. It also claimed an ETH lower bound excluding running time $\rho_p(d)L^{o(d)}$ , approximation barriers, and consequences for two-layer ReLU-network Lipschitz constants. The paper notes concurrent papers, but no supplied source establishes peer review or independent confirmation.

Current status (as of August 2026): The open fixed-parameter tractability question is claimed resolved negatively by a new preprint, while the claimed hardness and ETH consequences remain unverified.

Sources

No solutions have been posted yet.

LpL_pLp​-Lipschitz constants of two-layer input-convex neural networks

Primary source

Additional references

Progress summary

$L_p$ -Lipschitz constants of two-layer input-convex neural networks