acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. Computing the -Lipschitz constant for two-layer input-convex neural networks (ICNNs) is equivalent to maximizing the dual norm over a zonotope. While - and -norm maximization on zonotopes are fixed-parameter tractable and polynomial-time solvable, respectively, the parameterized complexity of the remaining -norms was open. We prove that, for every fixed , maximizing the -norm over a zonotope in is W[1]-hard with respect to the dimension . Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the -Lipschitz constant of a two-layer ReLU ICNN. Our paper resolves an open problem posted at COLT '25 (Froese et al. 2025). There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying geometric ideas and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Parameterized Reductions, Exponential Time Hypothesis, Polyhedral Geometry, Neural Network Robustness

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 4 reviews, above 85% of the others.
Reviewer_k2x1OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates the computational complexity of computing exact LpL_p-Lipschitz constants for two-layer ReLU input-convex neural networks (ICNNs), focusing on whether these problems become tractable when parameterized by the input dimension dd. The authors establish an equivalence between computing the Lipschitz constant of an ICNN and maximizing the corresponding dual norm over a zonotope.

The main contribution is proving that, for every fixed rational p∈(1,∞)p\in(1,\infty), exact LpL_p-norm maximization over zonotopes and exact LpL_p-Lipschitz constant computation for two-layer ReLU ICNNs are W[1]-hard with respect to dd. Under the Exponential Time Hypothesis (ETH), they further establish that no exact algorithm can achieve a running time of ρ(d)No(d)\rho(d)N^{o(d)}, implying that existing enumeration-based algorithms are essentially optimal in their asymptotic dependence on dimension. The proof uses a reduction from Multicolored Clique to L2L_2-norm maximization over zonotopes, followed by a construction extending the hardness result to general rational p∈(1,∞)p\in(1,\infty). These findings address an open problem from COLT 2025, although the authors acknowledge concurrent independent results.

The validation is entirely theoretical, relying on formal complexity reductions, geometric constructions, and mathematical proofs. The paper provides two alternative hardness reductions but does not include numerical experiments, computational benchmarks, or empirical evaluations on neural networks. Consequently, its contribution is primarily to establishing worst-case computational hardness rather than developing or validating a practical Lipschitz estimation algorithm.

Critical strengths

The paper resolves an open problem from COLT 2025 by establishing W[1]-hardness for computing exact LpL_p-Lipschitz constants of two-layer ReLU ICNNs for every fixed rational p∈(1,∞)p\in(1,\infty). Furthermore, the ETH-based lower bound rules out algorithms with running time ρ(d)No(d)\rho(d)N^{o(d)}, providing a strong characterization of the computational difficulty. This counts towards contribution because it establishes that input convexity alone does not guarantee tractability and clarifies the fundamental limitations of exact Lipschitz computation.

Critical weaknesses

Although the paper addresses an important open problem from COLT 2025, its main theoretical results substantially overlap with several concurrent works acknowledged in Section 1.2. In particular, Cao et al. (2026) establish W[1]-hardness for general rational p∈(1,∞)p\in(1,\infty), along with related ETH-based lower bounds and approximation results. While this paper provides a different geometric construction and improves the reduction dimension to 2k2k for the L2L_2 case, it is unclear whether these differences lead to fundamentally stronger theoretical conclusions or broader implications. The main contribution therefore appears to be an alternative proof of results that have already been independently established. This limits the incremental novelty of the work and is my primary concern regarding acceptance.

Questions for authors
  1. Novelty relative to concurrent work

The paper acknowledges several concurrent works that establish similar W[1]-hardness results for LpL_p-norm maximization over zonotopes. Could the authors clarify the main theoretical advantages of their approach beyond the improved reduction dimension and geometric interpretation? In particular, does the proposed geometric construction enable any stronger complexity results or extensions that are not readily obtainable from existing reductions? Clarifying these distinctions would help assess the novelty and significance of the contribution relative to concurrent work.

  1. Implications for approximate and practical Lipschitz certification

The paper establishes hardness for exact global LpL_p-Lipschitz constant computation, while practical neural-network certification often relies on approximate bounds or domain-restricted Lipschitz estimates. Could the authors clarify whether their hardness constructions imply any meaningful limitations for approximate Lipschitz certification, such as computing bounds within a prescribed relative error, or for Lipschitz estimation over bounded input domains? Understanding which aspects of practical certification are affected by these hardness results would help assess the broader significance and applicability of the theoretical findings.

2 comments

Thank you for your careful reading and evaluation of our paper, and for your feedback. We believe we have addressed all raised questions in the responses below, and we are happy to answer any further questions.

  1. Novelty relative to concurrent work The paper acknowledges several concurrent works that establish similar W[1]-hardness results for LpL_p-norm maximization over zonotopes. Could the authors clarify the main theoretical advantages of their approach beyond the improved reduction dimension and geometric interpretation? In particular, does the proposed geometric construction enable any stronger complexity results or extensions that are not readily obtainable from existing reductions? Clarifying these distinctions would help assess the novelty and significance of the contribution relative to concurrent work.

Please see our general response for a discussion regarding our views on the novelty of our paper in light of the concurrent works. Additionally, we believe that the implicit technique (in particular, Proposition 4.2) that we used in the reduction of Section 4 is of interest on its own and could be applicable to other geometric problems involving zonotopes.

  1. Implications for approximate and practical Lipschitz certification The paper establishes hardness for exact global LpL_p-Lipschitz constant computation, while practical neural-network certification often relies on approximate bounds or domain-restricted Lipschitz estimates. Could the authors clarify whether their hardness constructions imply any meaningful limitations for approximate Lipschitz certification, such as computing bounds within a prescribed relative error, or for Lipschitz estimation over bounded input domains? Understanding which aspects of practical certification are affected by these hardness results would help assess the broader significance and applicability of the theoretical findings.

Since the function used in our construction is positively homogeneous, the hardness results transfer also to computing Lipschitz constants over bounded input domains (as long as the domain contains an open set around the origin). For example, hardness holds for computing the Lipschitz constant on λ⋅Bp\lambda\cdot \mathcal{B}_p (for any λ>0\lambda>0) for any scaled version of the LpL_p-unit ball Bp={x∈Rd:∥x∥p≤1}\mathcal{B}_p=\{x\in \mathbb{R}^d: \|x\|_p\leq 1\}. We have included this in Section 5 of the paper (line 488-490).

As indicated in our response to Reviewer ArH7, our explicit reduction in the appendix implies that computing the LpL_p-Lipschitz constant within a relative error of ε=1/poly⁡(n)\varepsilon=1/\operatorname{poly}(n) is W[1]-hard for all fixed p∈(1,∞)∩Qp\in (1,\infty)\cap \mathbb{Q}. Regarding constant-factor approximation, the (1−ε)(1-\varepsilon)-approximation FPT algorithm of Shenmaier 2018 shows that approximation is tractable for small input dimensions. We now also discuss practical implications of our results in Section 6.

Thank you for the response and the clarifications. Following the ICLR policy, I no longer weigh the concurrent results discussed in Section 1.2 against the submission, as they appeared only recently and are not peer-reviewed. The paper resolves the open problem posed at COLT 2025, and the novelty of the contribution stands. I have raised my score to 3.

Reviewer_KE5bOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper shows that computing the L_p - Lipschitz constant of ICNN is W[1] - hard. There are few concurrent works that prove a similar result; they use a known result that for two-layer ICNNs finding the L_p Lipschitz constant is equivalent to maximizing the L_q norm over a certain zonotope, and reduce the problem to multicolored clique problem.

Critical strengths

The main strength is the paper is easy to follow. The notations are well-written, the definition of problems, their geometric intuition, how a reduction is done from one problem from another are all well defined, and the relevant figures that explain certain concepts are in the right spot. This is I think from the fact that even though the proof got some AI assistance, all visualization/presentation were made by the authors.

Another very good strength is that concurrent work that prove similar things are explained. I believe the problem was introduced as an open problem and people have tried and succeeded solving these problems using AI, and they explicitly show that there are similar concurrent work. I think this is good academic integrity.

Critical weaknesses

The one weakness is that there is concurrent work that uses the same multicolored clique [1]. However, I reviewed the paper and I think the paper did a good job explaining the hidden idea behind the proof much better.

[1] Yang Cao, Haoran Qi, and Hanzhi Wang. ℓp-norm maximization over zonotopes is W[1]-hard. arXiv preprint arXiv:2608.15847, 2026.

Questions for authors

In the AI use statement I could see that LLMs proposed the initial version of the reduction. I am curious on what extend this was - was the reduction complete, or was the connection with Multicolored clique proposed?

2 comments

Thank you for your careful reading and evaluation of our paper, and for your positive feedback. We believe we have addressed all raised questions in the responses below, and we are happy to answer any further questions.

In the AI use statement I could see that LLMs proposed the initial version of the reduction. I am curious on what extend this was - was the reduction complete, or was the connection with Multicolored clique proposed?

In both initial versions of the reductions, the LLMs proposed reductions from Multicolored Clique which is not surprising since Multicolored Clique is commonly used to prove W[1]-hardness (and has also been used to prove hardness for various related problems, e.g., in Froese et al. 2026). However, as mentioned in Section 7, the proposed reductions by the LLMs were not completely correct. However, after extracting the key ideas from the proposed reductions, we were able to arrive at correct reductions using these key ideas.

I think my initial evaluation was fair and I maintain my score.

Reviewer_MDFDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper is well written in sense of math. Estimating lipschitz constant of networks is research line under the umbrella of robustness.

Computing the exact global LpL_p-Lipschitz constant of a neural network is known to be NP-hard. For restricted conditions, eg 2-layer input-convex networks, Froese et al. [1] raised the question of whether exact computation is FPT (fixed-parameter tractable) with respect to input dimension. I think this work is an application/response in lipschitz estimation research line to the call in [1]. Claiming of solving an open problem might be over claim. This work establishes W[1]W[1]-hardness and ETH-based running-time lower bounds.

Note. i feel some results no longer hold in this work since ETH hypothesis might be false.

[1] Froese et al. Open Problem: Fixed-Parameter Tractability of Zonotope Problems. COLT 2025.

Critical strengths
  1. well written.
  2. nice literature engagement. I used ChatGPT for verifying the bibliography. they look correct.
  3. well motivated. I think the motivation is quite clear.
Critical weaknesses

my major concern is the significance and no experimental evaluation.

  1. Limited significance. I am not convinced the significance of this work for computing the lipschitz constant of a restricted 2 layer input-convex network. while theoretically interesting, the significance for modern deep neural networks remains unclear. In particular, there exist an extensive research line for estimating/computing Lipschitz constant of general networks.

what is the niche and how to justify this?

  1. related work. this work falls in the research line of estimating/computing network lipschitz. it should have literature review (brief reviewing in one paragraph is sufficient).

  2. overclaims. this work over-claim that it resolves an open problem in [1].

  3. limited theoretical contributions. I skimmed [2] and [3]. and feel some claims eg W[1]W[1]-hardness overlaps with eg [2-3]. Although the proposed geometric reductions differ, it does't convincingly demonstrate their actual contributions.

  4. Lack of empirical evaluation. estimating lipschitz of networks is an extensive research line. to be a sound work. this work is expected to have empirical validation and evaluation against baselines. I didn't see that and this not convince me the performance and soundness.

  5. ETH. If ETH is false, the work needs to prove not relying on ETH hypothesis. I skimmed your proofs. I don't think you need to use ETH.

[1] Froese et al. Open Problem: Fixed-Parameter Tractability of Zonotope Problems. COLT 2025.

[2] ℓp\ell_p-Norm Maximization over Zonotopes Is W[1]W[1]-Hard, https://arxiv.org/pdf/2608.15847

[3] Convex Networks Remain Hard to Certify: Dimension-Accuracy Barriers for Lipschitz Constants https://arxiv.org/abs/2608.16150

Questions for authors

see the weaknesses I summarised.

also, can you explain/clarify L263-269? I'm confused by the bijection.

3 comments

Thank you for your careful reading and evaluation of our paper, and for your feedback. We believe we have addressed all raised questions in the responses below, and we are happy to answer any further questions.

  1. Limited significance. I am not convinced the significance of this work for computing the lipschitz constant of a restricted 2 layer input-convex network. while theoretically interesting, the significance for modern deep neural networks remains unclear. In particular, there exist an extensive research line for estimating/computing Lipschitz constant of general networks. what is the niche and how to justify this?

Note that proving hardness for a restricted class (in our case, two-layer ICNNs) is a stronger statement than proving hardness for the general class. This is because every architecture class that contains two-layer ICNNs (deeper ICNNs, general ReLU networks) inherits the hardness. Previously, the problem of computing the LpL_p-Lipschitz constant was already known to be W[1]-hard for general ReLU networks, and it was known that computing the L1L_1- and L∞L_\infty-Lipschitz constant is fixed-parameter tractable for ICNNs of arbitrary depth. Therefore, it was a natural open question whether this problem is also fixed-parameter tractable for all other LpL_p-norms with p∈(1,∞)p\in (1,\infty). Our results answer this question negatively in the strongest way, as we show W[1]-hardness already for ICNNs with just one hidden layer. Our theoretical results therefore explain why existing algorithms for computing Lipschitz constants have to scale exponentially in the input dimension even for ICNNs (unless Multicolored Clique can be solved in no(k)n^{o(k)} time).

  1. related work. this work falls in the research line of estimating/computing network lipschitz. it should have literature review (brief reviewing in one paragraph is sufficient).

We have added a paragraph with literature on estimating and computing the Lipschitz constant to our related work section (line 146-151).

  1. overclaims. this work over-claim that it resolves an open problem in [1].

  2. limited theoretical contributions. I skimmed [2] and [3]. and feel some claims eg W[1]W[1]-hardness overlaps with eg [2-3]. Although the proposed geometric reductions differ, it does't convincingly demonstrate their actual contributions.

Our Corollary 5.3 answers the open problem by Froese et al. (COLT 2025), who explicitly state the question in Section 2 "Is LpL_p-Maximization over dd-Zonotopes fixed-parameter tractable with respect to dd for p>1p > 1?" negatively for every rational p∈(1,∞)p\in (1,\infty), unless FPT=W[1]. We already acknowledge that (special cases of) this W[1]-hardness result were obtained independently by different groups with concurrent solutions and describe the differences and similarities of these concurrent results in Section 1.2. Please see the general answer above for a more in-depth answer regarding this concern.

  1. Lack of empirical evaluation. estimating lipschitz of networks is an extensive research line. to be a sound work. this work is expected to have empirical validation and evaluation against baselines. I didn't see that and this not convince me the performance and soundness.

The results in our paper are clearly theoretical and there are no reasonable experiments to evaluate worst-case running time lower bounds. However, we believe that our results are still of use also to practitioners and can inform practice (see our response to Q3 of Reviewer ArH7 for a discussion of practical implications that follow from our results, we now discuss them in Section 6).

  1. ETH. If ETH is false, the work needs to prove not relying on ETH hypothesis. I skimmed your proofs. I don't think you need to use ETH.

Our main result, the W[1]-hardness, is not affected even if the ETH is false. We obtained running time lower bounds conditional on the ETH only as a side result. Moreover, even if ETH is false, our running time lower bounds still hold under the hypothesis that Multicolored Clique is not solvable in no(k)n^{o(k)} time (which is still open, even if the ETH is false). We have updated our paper (we now state running time lower bounds under this hypothesis that does not depend on the ETH).

also, can you explain/clarify L263-269? I'm confused by the bijection.

The bijection φ\varphi maps convex and positively homogeneous CPWL functions from Rd\mathbb{R}^d to R\mathbb{R} of the form max⁡{a1⊤x,…,ak⊤x}\max\lbrace a_1^\top x,\dots, a_k^\top x\rbrace to polytopes conv⁡{ai:i∈[k]}\operatorname{conv}\lbrace a_i:i\in [k]\rbrace in Rd\mathbb{R}^d. This bijection comes from a well-known duality in tropical geometry (see e.g. "Introduction to tropical geometry", Maclagan&Sturmfels 2015 for more details). The equation in line 266 uses the fact that φ\varphi satisfies φ(f+g)=φ(f)+φ(g)\varphi(f+g)=\varphi(f)+\varphi(g). Applying this addition property to the function x↦∑imax⁡{0,wi⊤x}x\mapsto \sum_i \max\lbrace 0,w_i^\top x\rbrace gives φ(∑imax⁡{0,wi⊤x})=∑iφ(max⁡{0,wi⊤x})\varphi(\sum_i \max\lbrace 0,w_i^\top x\rbrace)=\sum_i \varphi(\max\lbrace 0,w_i^\top x\rbrace). Applying the definition of φ\varphi, we have φ(max⁡{0,wi⊤x})=conv⁡{0,wi}\varphi(\max\lbrace0,w_i^\top x\rbrace)=\operatorname{conv}\lbrace 0,w_i\rbrace, and thus ∑iφ(max⁡{0,wi⊤x})=∑iconv⁡{0,wi}\sum_i \varphi(\max\lbrace 0,w_i^\top x\rbrace)=\sum_i \operatorname{conv}\lbrace 0,w_i\rbrace, which is equal to Z(W⊤)Z(W^\top) by the definition of Z(⋅)Z(\cdot).

The bijection between regions of a hyperplane arrangement and vertices of a corresponding zonotope is a classical fact in polyhedral geometry (see Ziegler 2012 for details). Intuitively, consider a linear region of ff (which is a region of HWH_W) where exactly the neurons in II are active, that is, wi⊤x>0w_i^\top x>0 for all i∈Ii\in I and wi⊤x≤0w_i^\top x\leq 0 for all i∉Ii\notin I. On this linear region, f(x)=∑imax⁡{0,wi⊤x}=∑i∈Iwi⊤xf(x)=\sum_i \max\lbrace 0,w_i^\top x\rbrace=\sum_{i\in I} w_i^\top x, and the gradient of ff on this region is ∑i∈Iwi\sum_{i\in I} w_i, which is always a vertex of the zonotope Z(W⊤)Z(W^\top) (see also Figure 1 for an illustration).

Reviewer_MDFDOpenReview ↗

Thanks authors for their replies.

I thank the authors for their replies.

I remain the score (actually slightly it's a higher score in my batch) on the basis of the significance and method itself in lipschitz niche.

Reviewer_ArH7OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

===== Paper Summary =====

The paper resolves the COLT 2025 open problem (Froese et al., 2025a) on the parameterized complexity of computing the L_p-Lipschitz constant of two-layer ReLU input-convex neural networks (ICNNs), which by a tropical duality equals maximizing the dual L_q-norm over a generator-represented zonotope. Section 4 reduces MULTICOLORED CLIQUE to L_2-MAX ON ZONOTOPES in dimension d = 2k: a node term built from rational points on the unit circle gives a support function equal to 1 - dist(y,T)^2/2 on the sphere, and an edge term encodes adjacency through Lemma 4.1 (the all-ones vector lies in the interior of the cone of zonotope support-function values on equal-norm points) and an LP (Proposition 4.2). Section 5 transfers L_2^2 hardness to L_p^p for every fixed rational p in (1, inf) by embedding the zonotope into the tangent hyperplane at the all-ones vector (Proposition 5.1), and a rational-threshold argument covers L_p itself. This yields W[1]-hardness in d and a rho(d) N^{o(d)} ETH lower bound matching vertex enumeration. Appendix B gives an explicit 2k+1 reduction, and Section 7 documents LLM use and three concurrent resolutions.

Critical strengths

===== Critical Strengths =====

S1. The paper settles a clearly posed open problem with a tight answer. For every fixed rational p in (1, inf), exact L_p-norm maximization over zonotopes and the two-layer ICNN L_p-Lipschitz constant are W[1]-hard in d and admit no rho(d) N^{o(d)} algorithm under the ETH, so n^{d-1} vertex enumeration (Ferrez et al., 2005) is essentially optimal and input convexity does not help beyond L_1 and L_inf. I checked the distance identity in Lemma A.1, the completing-the-square step with eta = delta*/(8 Lambda^2) in Theorem 4.3, the constants in Lemma A.3 and the choice of epsilon in Proposition 5.1, and Lemma B.1 with the constants of Theorem B.2, and found no errors.

S2. Proposition 5.1 is a clean and reusable idea. Embedding Z(A) antisymmetrically as x -> (x, -x) into the tangent hyperplane at 1_{2d}, where the first-order term vanishes and the Hessian of ||.||_p^p is p(p-1)I, turns L_p^p-maximization into L_2^2-maximization up to a fourth-order error. This avoids constructing rational points on the L_p circle (the Fermat obstruction discussed in Appendix B), and Lemma A.4 handles the irrational L_p threshold correctly. The two reductions with stated intuition, and the candid account of LLM use in Section 7, make the paper easy to verify and a useful reference.

Critical weaknesses

W1. The contribution beyond the concurrent resolutions is narrower than the paper suggests, and this is the main reason my rating is not higher. I do not hold concurrency against the authors, but the claimed differentiators should be accurate. First, dimension: 2k versus 2k+1 is an additive constant with no effect on the n^{o(d)} bound, and it holds only for p = 2, since Proposition 5.1 doubles the dimension and the proof of Theorem 5.2 gives D = 4k. For general p, the construction is therefore larger than the 2k+1 reduction of Cao et al. (2026), who also prove the L_p^p result and add FPT (1 - eps)-approximation algorithms with a matching (1/eps)^{o(d)} lower bound. Second, Lemma 4.1 is presented as a new geometric observation, but its key step, that the spherical average of |w^T s| equals c_U ||s||, is the classical fact that the Euclidean ball is a zonoid (cosine transform of the uniform measure; Bolker, 1969; Schneider's monograph on convex bodies). Lemma 4.1 and Proposition 4.2 should be positioned against zonoid theory, and the 2k claims in Sections 1.1 and 1.2 toned down. What remains distinctive is mainly Proposition 5.1 and the exposition.

W2. The machine-learning significance is limited and not discussed. The ICNN connection is the known duality of Froese et al. (2025a), so Section 3 is the only ML-specific content and the result is effectively a statement about zonotopes. More importantly, the hard instances need weights whose bit-length grows with the graph: the generators in Theorem 4.3 come from LP solutions with no stated size bound and are scaled by eta = delta*/(8 Lambda^2), Proposition 5.1 scales by an epsilon proportional to Delta/(d C_p R^2), and Appendix B uses Lambda on the order of m^2 n^4. If weights are integers of magnitude at most 2^b, positively parallel generators merge, so there are at most 2^{O(bd)} distinct generators and vertex enumeration runs in f(d, b) poly(N) time; the problem is FPT in (d, b), and the hardness is a high-precision phenomenon. This matters for quantized networks, which Ganian et al. (2026) treat as a natural parameter. Finally, the practically relevant task is approximation, where FPT (1 - eps)-schemes already exist (Shenmaier, 2018; Froese et al., 2026), so the paper should state what exact hardness implies for certifying L_2-Lipschitz bounds of ICNNs in practice.

Other issues (not decisive): the nonlinearity step in the proof of Lemma 4.1 is informal and should argue at a point of H_m within U that lies on no other H_i; no bound is given on the bit-length of the LP-derived generators or of delta_ij; notation clashes (k is both the clique size and the binary-search step count in Lemma A.4, p is both the norm exponent and a node index in Appendix B, and Lemma A.2 writes s_{a,b,tau}); the cyclic relabeling of u_{i,r} in Lemma A.1 is consistent only because the original u_{i,1}, ..., u_{i,n_i} already appear counterclockwise within a half-plane, which should be stated; and Footnote 1 should give a date or commit for the concurrent pipeline proof.

Questions for authors

===== Questions For Authors =====

Q1 addresses W1, and Q2 and Q3 address W2.

Q1. What exactly do Lemma 4.1 and Proposition 4.2 add beyond the representation of the Euclidean ball as a zonoid and known interpolation results for zonoid support functions? Can a direct L_p version of the Section 4 reduction, or a variant of Proposition 5.1, achieve dimension below 4k for p != 2, and does the 2k versus 2k+1 distinction affect any bound you prove?

Q2. Can you give explicit bit-length bounds for A_G in Theorem 4.3? Do the hardness results persist when weights are integers of bounded magnitude, or is TWO-LAYER ICNN L_p-LIPSCHITZ CONSTANT FPT in (d, b) by the merging argument in W2? A short discussion of which parameter combinations remain open would sharpen the ML message.

Q3. Do your reductions imply any inapproximability, for example a lower bound on the relative gap Delta/L as a function of n, that complements the known FPT (1 - eps)-approximation schemes? What should a practitioner computing L_2-Lipschitz bounds of ICNNs conclude from the result: target approximation, restrict the architecture, or bound the weight precision?

3 comments

Thank you for your careful reading and evaluation of our paper, and for your detailed feedback. We believe we have addressed all raised questions in the responses below, and we are happy to answer any further questions.

W1. The contribution beyond the concurrent resolutions is narrower than the paper suggests, and this is the main reason my rating is not higher. I do not hold concurrency against the authors, but the claimed differentiators should be accurate. First, dimension: 2k versus 2k+1 is an additive constant with no effect on the n^{o(d)} bound, and it holds only for p = 2, since Proposition 5.1 doubles the dimension and the proof of Theorem 5.2 gives D = 4k. For general p, the construction is therefore larger than the 2k+1 reduction of Cao et al. (2026), who also prove the L_p^p result and add FPT (1 - eps)-approximation algorithms with a matching (1/eps)^{o(d)} lower bound.

Q1. Can a direct L_p version of the Section 4 reduction, or a variant of Proposition 5.1, achieve dimension below 4k for p != 2, and does the 2k versus 2k+1 distinction affect any bound you prove?

Please see our general response for a discussion regarding our views on the novelty of our paper in light of the concurrent works.

The purpose of the comparison of the dimensionalities in Section 1.2 was to highlight the fact that the reductions are all quite different. We do not claim to "improve" on the concurrent works. In fact, all works prove W[1]-hardness for (special cases of) p∈(1,∞)∩Qp\in (1,\infty)\cap \mathbb{Q} (as described in Section 1.2) and the reductions from Multicolored Clique have dimensions linear in kk (2k2k, 2k+12k+1, and 4k4k). So they yield the same asymptotic running time lower bounds. We have revised the last sentence of the concurrent work section to make it clear that our reduction has dimension 4k4k for p≠2p\neq 2 (line 142). While it might be possible to achieve dimensionality below 4k4k by modifying our reduction, this would not affect or strengthen any running time lower bounds.

Second, Lemma 4.1 is presented as a new geometric observation, but its key step, that the spherical average of |w^T s| equals c_U ||s||, is the classical fact that the Euclidean ball is a zonoid (cosine transform of the uniform measure; Bolker, 1969; Schneider's monograph on convex bodies). Lemma 4.1 and Proposition 4.2 should be positioned against zonoid theory, and the 2k claims in Sections 1.1 and 1.2 toned down. What remains distinctive is mainly Proposition 5.1 and the exposition.

Q1. What exactly do Lemma 4.1 and Proposition 4.2 add beyond the representation of the Euclidean ball as a zonoid and known interpolation results for zonoid support functions?

Thank you very much for mentioning the connection to zonoid theory. After looking deeper into the zonoid literature, we found a paper by Campi et al. 1994 [1] that proves results about zonoids which are closely related to our Proposition 4.2. While we have not yet worked out the details, it seems likely that our Proposition 4.2 can be proven by showing that there exists a suitable zonoid and then applying Theorem 1 of [1]. We believe this does not affect the significance of our results, since it is not the validity of this geometric observation that we find interesting, but instead the idea to use it for a hardness reduction which we believe can be a powerful method also for other problems involving zonotopes. Although Lemma 4.1 and Proposition 4.2 might be provable in a simpler way using zonoid theory, proving the results in this way would in turn require explaining the basics of zonoid theory in our paper, which would make the paper, in our opinion, less accessible to readers that are not familiar with this topic. We therefore believe that keeping our self-contained proofs of Lemma 4.1 and Proposition 4.2 makes the paper more accessible. Nevertheless, we find this connection to zonoids very interesting and now mention this connection and the related result in our paper (line 350-351). Further, we believe that exploring possible applications of results from zonoid theory to hardness reductions for problems involving zonotopes could be an interesting direction for future work.

[1] Campi, S., Haas, D., & Weil, W. (1994). Approximation of zonoids by zonotopes in fixed directions. Discrete & computational geometry, 11(4), 419-431.

W2. The machine-learning significance is limited and not discussed. The ICNN connection is the known duality of Froese et al. (2025a), so Section 3 is the only ML-specific content and the result is effectively a statement about zonotopes. More importantly, the hard instances need weights whose bit-length grows with the graph: the generators in Theorem 4.3 come from LP solutions with no stated size bound and are scaled by eta = delta*/(8 Lambda^2), Proposition 5.1 scales by an epsilon proportional to Delta/(d C_p R^2), and Appendix B uses Lambda on the order of m^2 n^4. If weights are integers of magnitude at most 2^b, positively parallel generators merge, so there are at most 2^{O(bd)} distinct generators and vertex enumeration runs in f(d, b) poly(N) time; the problem is FPT in (d, b), and the hardness is a high-precision phenomenon. This matters for quantized networks, which Ganian et al. (2026) treat as a natural parameter. Finally, the practically relevant task is approximation, where FPT (1 - eps)-schemes already exist (Shenmaier, 2018; Froese et al., 2026), so the paper should state what exact hardness implies for certifying L_2-Lipschitz bounds of ICNNs in practice.

Q2. Can you give explicit bit-length bounds for A_G in Theorem 4.3? Do the hardness results persist when weights are integers of bounded magnitude, or is TWO-LAYER ICNN L_p-LIPSCHITZ CONSTANT FPT in (d, b) by the merging argument in W2? A short discussion of which parameter combinations remain open would sharpen the ML message.

It is true that a W[1]-hardness reduction requires weights of arbitrary precision, since in the setting where all rational weights have encoding size at most bb, there are at most 2O(db)2^{O(db)} distinct generators and vertex enumeration then takes 2O(bd2)poly⁡(N)2^{O(bd^2)}\operatorname{poly}(N) time, showing that the problem is in FPT for the parameter (b,d)(b,d). Therefore, any reduction proving W[1]-hardness necessarily involves weights which cannot be bounded in~dd alone. We now mention this in Section 1.3 of the paper (lines 168-173).

Regarding the bit size of AGA_G: Since the bit-length of the entries of the generator matrix AGA_G in Theorem 4.3 relies on the bit-length of the generators that come from the solution of the linear program, we can only give very rough polynomial bounds that follow from LP theory. However, each entry in the generator matrix that we construct in the alternative, explicit proof of Theorem B.2 has encoding size O(log⁡n)O(\log n). Also after applying Proposition 5.1 to the instances of Theorem B.2, the entries of the "hard" matrices AGA_G have encoding size O(log⁡n)O(\log n). Therefore, W[1]-hardness holds for all fixed p∈(1,∞)p\in (1,\infty) when the rational weights have polynomially bounded (in nn) numerators and denominators.

Regarding the relevance for ML: zonotopes and zonotope-norm maximization in general appear also in various other ML-related contexts. For example, LpL_p-norm maximization over zonotopes appears as the final step of the algorithm in [2] for Lipschitz constant estimation of neural networks, and zonotope-based methods are used frequently in neural network verification (see e.g. [3-5] and the references therein). We have included these references in our related work section (lines 146-151).

[2] Jordan & Dimakis. Provable Lipschitz certification for generative models. ICML 2021.

[3] Singh et al. Fast and effective robustness certification. NeurIPS 2018.

[4] Kochdumper et al. Open-and closed-loop neural network verification using polynomial zonotopes. In NASA Formal Methods Symposium 2023.

[5] Koller et al. Set-Based Training for Neural Network Verification. TMLR 2025.

Q3. Do your reductions imply any inapproximability, for example a lower bound on the relative gap Delta/L as a function of n, that complements the known FPT (1 - eps)-approximation schemes? What should a practitioner computing L_2-Lipschitz bounds of ICNNs conclude from the result: target approximation, restrict the architecture, or bound the weight precision?

For the L22L_2^2-instances constructed in Theorem B.2, we have L=O(m4n9)L=O(m^4n^9) and Δ=m2\Delta=m^2, where nn and mm are the number of nodes and edges of the Multicolored Clique instance. Therefore, computing a (1−ε)(1-\varepsilon)-approximation of max⁡z∈Z(AG)∥z∥22\max_{z\in Z(A_G)}\|z\|_2^2 is W[1]-hard for ε=Δ/L=Ω(1m2n9)\varepsilon=\Delta/L=\Omega\left(\frac{1}{m^2n^9}\right). Proposition 5.1 then implies W[1]-hardness of approximation for ε=1/poly⁡(n)\varepsilon=1/\operatorname{poly}(n) for all fixed p∈(1,∞)∩Qp\in (1,\infty)\cap \mathbb{Q}.

The main takeaway for practitioners is that exact computation is intractable, whereas approximation for low input dimension can be done efficiently. Also, working with quantized neural networks could be an alternative for low input dimensions. However, most importantly, if there is no particular need to work with L2L_2-Lipschitz constants, one should instead work with L1L_1-Lipschitz constants, as they can be computed in polynomial time. Finally, as mentioned in the response to Reviewer 4, the problem for LpL_p-norms is still hard if one restricts to bounded domains. We now mention these practical implications in our Section 6.

Other issues (not decisive): the nonlinearity step in the proof of Lemma 4.1 is informal and should argue at a point of H_m within U that lies on no other H_i; no bound is given on the bit-length of the LP-derived generators or of delta_ij; notation clashes (k is both the clique size and the binary-search step count in Lemma A.4, p is both the norm exponent and a node index in Appendix B, and Lemma A.2 writes s_{a,b,tau}); the cyclic relabeling of u_{i,r} in Lemma A.1 is consistent only because the original u_{i,1}, ..., u_{i,n_i} already appear counterclockwise within a half-plane, which should be stated; and Footnote 1 should give a date or commit for the concurrent pipeline proof.

Thank you very much for mentioning these points. For a discussion about bit-lengths, please see our answer to Q2. We have incorporated the rest of the comments into our paper (see lines 161, 754-757, 798-799, 843, 1101, 1236).

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

With this response, we aim to address the concern regarding the novelty of our main result given that the same result was obtained independently in concurrent work.

The open problem of Froese et al. (COLT 2025) was resolved independently by at least four groups within a few weeks: an agentic pipeline (Github, July 8, not on arXiv), Cao et al. (arXiv, August 16), Dewasurendra & Jayawardhana (arXiv, August 17), and ourselves (as indicated in Section 7, our reductions were originally found in May). None of these works has appeared in a peer-reviewed venue, and all appeared within roughly two months before the submission deadline. The ICLR Guidelines do not require authors to compare their work to papers that are only available on arXiv or in non-peer-reviewed venues, and states that "the lack of such comparisons cannot be a basis for rejection". However, we strongly believe that it is valuable for readers to understand how the different approaches in our work and the concurrent works relate, which is why we included such a discussion in Section 1.2, and would be grateful if this transparency is not counted against us.

As AI tools become increasingly more capable, we do not find it surprising that a result such as this one was found independently by several groups (given that it was prominently posed as an open question). While this incentivizes publishing results as quickly as possible, we deliberately took several months to create a high-quality, understandable, and easy-to-verify exposition before making the result public. We did our best to provide intuition and explain the underlying geometric ideas of the proof and believe that producing digested mathematics has value in itself. We are happy to see that most reviewers found the presentation clear and easy to follow.

Finally, despite some similarities, all concurrent proofs use different techniques (see Section 1.2 for more details). Compared to the concurrent works, our paper contains

  • a reduction (in Section 4) that is based on a gadget that encodes the structure of an arbitrary bipartite graph into the support function of a centrally symmetric zonotope whose generators are computed via a linear program. We think that the application of this technique is interesting on its own and could be of use also for other problems involving zonotopes.
  • a second, explicit reduction that uses elementary techniques and is easy to verify.
  • Proposition 5.1, which transfers hardness from the L22L_2^2-case to the LppL_p^p-case for every fixed rational p∈(1,∞)p\in (1,\infty) which can be applied to any reduction for the L22L_2^2 case that produces a gap between yes- and no-instances.

Taking into account the comments from the reviews, we have uploaded a revised version of our paper to address the comments (we explicitly state in the individual responses below what changes we have made). All changes compared to the submission version are highlighted in red.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.