{"id":"1f4bcacc-ed2f-483f-a1a8-d87b7e85ae3d","arxiv_id":"1908.02824","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"It is NP-hard to approximate the hyperspherical radius of triangulated surfaces and triangulated high-dimensional spheres to within any almost-polynomial factor.","lead":"This paper proves that even approximating a basic geometric quantity, the hyperspherical radius of a triangulated manifold, is computationally intractable unless P equals NP. The result connects metric geometry to hardness of approximation, showing that a natural invariant studied since Gromov cannot be efficiently estimated in general.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central reduction rests on an unverified refinement of Dinur's SVP∞ theorem (Thm 4.4); if the YES-case short vector cannot be taken as u0 + Σ a_j u_j with a_j ∈ {0,1} and norm exactly 1, the gap in §4 fails.","rationale":"Theorem 1.1's hardness gap is inherited entirely from Theorem 4.4. The construction of X in §4 gives a clean equivalence between comass and l∞ norm, but the endpoint of the reduction is exactly the special shape of the short vector in the YES case. Without the 0/1 coefficient form with a0 fixed to 1, the quantities L≠0(X,h) and L1(X,h) could be small in both cases, destroying the gap. The authors' Section 4.1 is explicitly only 'an idea' and does not prove the refinement. This is not an accusation of error; it is a verification gap in a load-bearing external step. A direct check of Dinur's Proposition 22 would settle it. The rest of the paper—the comass/Lipschitz comparison, the LP computation, and the girth arguments for surfaces and spheres—is logically subordinate to this step for the stated theorem, though it appears sound. Hence I would not reject, but would make acceptance conditional on the verification of Theorem 4.4.","tokens_in":16631,"tokens_out":15499,"duration_ms":179003,"concrete_test":"Obtain Dinur [5] and trace the reduction from SAT to SVP∞ through the SSAT∞ → SVP∞ step, checking specifically that Proposition 22 of [5] produces in the YES case a lattice vector of the form u0 + Σ_{j=1}^M a_j u_j with all a_j ∈ {0,1} and l∞-norm exactly 1, with basis vectors of polynomial l∞ norm. If the check fails, Theorem 4.4 is false as stated; if it passes, the reduction in §4 goes through.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Theorem 1.1 is obtained by reducing from Theorem 4.4, a refinement of Dinur's SVP∞ hardness in which the YES instance contains v = u0 + Σ_{j=1}^M a_j u_j with a_j ∈ {0,1} and ‖v‖∞ = 1, while the NO instance has no nonzero lattice vector of norm ≤ N^{C/log log N}. The authors state that this refinement follows from inspecting the proof of Theorem 4.3 and locate condition (a) in Proposition 22 of [5], but they do not reproduce the verification. This is load-bearing: the gap for L≠0(X,h) and L1(X,h) in Theorem 4.2 uses the coefficient a0 = 1 and the 0/1 form to identify the class β = [Σ0]^* + Σ a_j[Σ_j]^* with comass 1, and uses the NO-case lower bound to force every nonzero β to have large comass. If Dinur's construction only guarantees a short vector of some other coefficient shape—for example coefficients in {-1,0,1}, or with a0 free to be 0—the minimum over a0 ≠ 0 or a0 = 1 could drop to a small value in the hard case, and the almost-polynomial gap disappears. Section 4.1 is explicitly only 'an idea' of Dinur's proof and does not close this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that, assuming P ≠ NP, it is NP-hard to approximate the hyperspherical radius of a triangulated manifold to within a factor N^{c / log log N}, where N is the volume and c > 0 depends on the dimension. The main theorem covers triangulated surfaces of arbitrary genus for n = 2 and triangulations of S^n for n ≥ 3, for both the non-zero-degree quantity L_{\\neq 0} and the degree-one quantity L_1. The proof develops a connection between the Lipschitz constant of maps to a sphere and the comass of cohomology classes, gives a polynomial-time LP approximation of comass, reduces from a refined version of Dinur's SVP_∞ hardness theorem to a simplicial complex X, and then embeds X as a small-girth surface or sphere. An appendix shows that the quantities admit constant-factor approximation by an NP optimization algorithm.","tokens_in":16902,"tokens_out":18711,"duration_ms":216273,"significance":"If the proof is correct, this is a striking and important result: it shows that a natural and geometrically meaningful quantity in metric geometry is hard to approximate in a strong sense, sharply contrasting with the known polynomial-time constant-factor algorithm for triangulated 2-spheres. The paper contains several genuinely valuable components: a full proof of Theorem 2.1 relating comass to Lipschitz constants, a clean LP-based algorithm for comass, a careful construction of high-genus surfaces imitating a given complex, and a useful NP certificate in the appendix. The main geometric idea of reducing from lattice problems through comass is elegant and likely to be influential. However, the proof as written has several load-bearing gaps that need to be addressed before the theorem can be considered established.","major_comments":[{"comment":"The hardness proof rests on a refinement of Dinur's SVP_∞ theorem that is not proved in the manuscript. The paper states that the refinement follows by inspecting the proof of Theorem 4.3 and that condition (a) appears in Proposition 22 of [5], but it does not reproduce the verification. The YES case requires a vector of the exact form v = u_0 + Σ a_j u_j with a_j ∈ {0,1} and ||v||_∞ = 1, and the NO case requires that no nonzero lattice vector has norm ≤ N^{C/log log N}. These exact properties are used to identify a cohomology class of comass 1 and to force the gap in Theorems 4.1 and 4.2. If Dinur's construction only yields a short vector of some other coefficient shape, for example with coefficients in {-1,0,1} or with a_0 free to be 0, the gap could collapse. Since Section 4.1 is explicitly only 'an idea' and does not supply the needed structural statement, the reduction is not yet fully supported.","section":"§4, Theorem 4.4"},{"comment":"The displayed formula for β([S_i]/(n+1)) sums j from 1 to M, omitting the j = 0 term. This is inconsistent with the construction, where the mapping cylinder attached to each S_i is in the class Σ_{j=0}^M (n+1) u_{ji} id_{Σ_j}, and it is inconsistent with the subsequent claims (a) and (b), which involve vectors containing u_0. As written, the identity ||v||_∞ = comass_Δ(γ(v)) for v = u_0 + Σ_{j=1}^M a_j u_j is false, because the contribution of u_0 to the coordinate cycles is dropped, and the lower bound comass_Δ(γ(v)) ≥ ||v||_∞ also fails for general v. The sums should run over j = 0,...,M. This is not a mere notational nuisance: the entire gap argument in Section 4 depends on the exact comass identity.","section":"§4, comass computation after construction of X"},{"comment":"The reduction for n = 2 requires Lip(g) ≲ Lip(f) in Lemma 5.1, but the lemma's bound is Lip(g) ≤ C(μ,n) ε^{-1}, where μ is the multiplicity of an ε-ball cover of X with Lebesgue number ε/2. For a unit-equilateral simplicial complex with unbounded valence, such a cover need not have multiplicity bounded independently of |X|: a high-valence vertex can force one point to lie in Ω(|X|) balls. The paper itself notes that no restrictions are placed on the combinatorics of X and that the number of facets incident to a vertex may be ∼ |X|. If C(μ,n) grows polynomially in |X|, the lower bound L_{\\neq 0}(Σ_s) ≥ min(s^{-1}, L_{\\neq 0}(X,h)/C(μ)) loses the N^{c/log log N} gap, since that gap is subpolynomial. The proof needs either a uniform multiplicity bound for the specific complexes X constructed in Section 4 or a different extension argument that does not introduce a polynomial factor depending on X.","section":"§5, Lemma 5.1 and proof of Theorem 1.1 for n = 2"},{"comment":"The proof of Lemma 6.2 is presented as a sketch and contains several steps that are not fully justified. In particular, the construction of pairwise disjoint paths p'_ij relies on assigning each pair a distinct distance from the middle of cubes and an entry/exit point, with the assertion that the paths map to different layers, but no proof is given that this can be done for all pairs simultaneously with polynomial size and without intersections. The later step 'we use the same technique as before to create non-intersecting sub-paths' inherits the same lack of detail. Since Lemma 6.2 is the bridge from the complex X to triangulated spheres S^n for n ≥ 3, and Theorem 1.1 for n ≥ 3 depends on it, this is a load-bearing gap. The lemma should either be proved in full or stated with a complete proof.","section":"§6, Lemma 6.2"}],"minor_comments":[{"comment":"There are several typos: 'repsectively' in the abstract, 'we define we define' in Section 4, and inconsistent spellings of 'Lipschitz' throughout. These should be corrected.","section":"Global"},{"comment":"The notation N^{C/log log N} is ambiguous: it should be written as N^{C/\\log\\log N} to make clear that the exponent is C/(log log N). The reader has to infer this from context.","section":"§1 and throughout"},{"comment":"The inequality chain at the end of the proof says N_Σ ≤ s^{-3}N^2 and 'so eventually ≤ N^{2.1}'. This is true only for sufficiently large N because s^{-3} = N^{3c/log log N} tends to 1 slowly; the proof should state this explicitly.","section":"§5, proof of Theorem 1.1 for n = 2"},{"comment":"The vector notation u_j = (u_{j0},...,u_{jN}) is confusing because the lattice is in Z^N but the tuple appears to have N+1 entries. Clarify that the coordinates are indexed i = 1,...,N, or use a different indexing convention.","section":"§4, notation for coordinates"}],"recommendation":"major_revision","confidential_remarks":"The paper has a compelling core idea and the main result is likely correct, but the proof currently depends on an unverified refinement of Dinur's theorem, an indexing error in the central comass computation, and a cover-multiplicity issue in the surface construction. These are substantial but plausibly fixable. I would be willing to look at a revised version that addresses them. The paper deserves a careful revision rather than rejection, because the geometric framework and the LP/comass connection are genuinely valuable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zara and I read the Brady–Guth–Manin paper on hardness of approximation for hyperspherical radius. The headline result is genuinely new: NP-hardness of approximating L≠0 and L1 for triangulated surfaces and triangulated spheres to within almost-polynomial factors, with a clean reduction from Dinur's SVP∞ hardness. The main geometric tool, the comass–Lipschitz comparison (Theorem 2.1), is proven in full and is a nice self-contained contribution. The LP approximation of comass in Section 3 is straightforward and correct. The surface case (n=2) uses a girth argument that is elegant and well explained.\n\nThe soft spots are where the reduction leans on unproven or sketched components. Theorem 4.4, the refined SVP∞ statement, is load-bearing: the YES case requires a short vector of the specific form u0 + Σ a_j u_j with a_j ∈ {0,1}. The authors say this follows by inspecting Dinur's proof, pointing to Proposition 22, but they do not reproduce the check. The stress-test note is right that this is not a triviality; if the vector had a different coefficient shape or a0 could vanish, the min over β with a0≠0 could drop. Section 4.1 is explicitly only an idea of Dinur's proof, so it doesn't close the gap. A referee familiar with Dinur's paper needs to verify this. I'm not willing to call it an error—it's likely true—but it's a real risk and the paper would be stronger with a full proof or a quote of the precise statement from a source that proves it.\n\nFor n ≥ 3, Lemma 6.2 is also sketched rather than fully proven. The construction of the simplicial sphere with controlled girth is plausible, but the non-intersecting path arguments and subdivision parameters need more detail. Again, this seems fillable, but it's the second place where the paper asks the reader to trust the authors.\n\nThe citation pattern is fine; the paper credits Guth, Ferry–Okun, Dinur, and the Chambers–Dotterrer–Manin–Weinberger work appropriately. The appendix gives an NP-algorithm upper bound, which is a nice complement.\n\nOverall, this is a serious paper with a new and important result. The core argument is clear, and the gaps are identifiable, external, and likely repairable. It deserves a careful referee, not a desk reject. I'd recommend sending it to a strong geometry/topology journal and asking the referee to specifically check Theorem 4.4 and Lemma 6.2. If those hold up, it's a clean paper.","headline":"A genuinely new NP-hardness result for hyperspherical radius, with a clean reduction from Dinur's SVP∞ hardness; the main caveat is an unverified refinement of Dinur's theorem and a sketchy algorithmic construction for n≥3.","tokens_in":17458,"tokens_out":3347,"would_cite":true,"duration_ms":34745,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["53C23","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Approximating a manifold's hyperspherical radius is NP-hard to within an almost-polynomial factor.","keywords":["hyperspherical radius","hardness of approximation","Lipschitz constant","comass","shortest vector problem","NP-hardness","quantitative topology","triangulated manifolds"],"falsifier":"Examine the cited shortest-vector proof to verify Theorem 4.4, or run the reduction on small SAT instances and search for a violation: a lattice where the shortest vector of the required 0/1 form has norm greater than 1, or where some other nonzero vector has norm below $N^{C/\\log\\log N}$. Either finding would break the chain from lattice hardness to $L_{\\neq 0}(X,h)$ and hence to Theorem 1.1.","tokens_in":16412,"feed_emoji":"📐","tokens_out":9287,"duration_ms":91543,"temperature":0.7,"pith_summary":"This paper proves that a basic geometric quantity, the smallest Lipschitz constant of a nonzero-degree map from a triangulated manifold to the unit sphere, cannot be approximated by any polynomial-time algorithm to within an almost-polynomial factor unless P equals NP. Equivalently, the hyperspherical radius of the manifold, which is the reciprocal of that constant, is NP-hard to approximate. The result covers triangulated surfaces of arbitrary genus when n=2 and triangulations of the n-sphere when n≥3, with the hardness factor $N^{c/\\log\\log N}$ where $N$ is the number of simplices. This matters because the hyperspherical radius is a natural metric invariant connected to scalar curvature and to the Novikov conjecture, and the proof shows the difficulty is combinatorial rather than geometric: it is inherited from a known NP-hard lattice problem.","feed_headline":"Finding a manifold's hyperspherical radius is NP-hard to approximate","feed_subtitle":"For triangulated surfaces and spheres, no polynomial-time estimate can get within $N^{c/\\log\\log N}$ unless $P=NP$.","key_machinery":"The argument's engine is the two-sided comparison, Theorem 2.1, between the Lipschitz norm of a homotopy class and the comass norm of its cohomology class:\n$$\\bigl(\\operatorname{vol}(S^n)\\,\\|\\$\\alpha$^*[S^n]\\|_{\\mathrm{comass}}\\bigr)^{1/n} \\le \\operatorname{Lip}(\\$\\alpha$) \\le C(\\dim X,n)\\bigl(\\|\\$\\alpha$^*[S^n]\\|_{\\mathrm{comass}}^{1/n}+1\\bigr).$$\nWhen the comass is at least 1, this determines $\\operatorname{Lip}(\\alpha)$ up to a constant depending only on dimension. Lemma 3.1 then computes the comass in polynomial time by linear programming. Hardness is injected by constructing $X$ as a wedge of $n$-spheres joined by mapping cylinders, so that the $\\ell^\\infty$ norm of a vector in the hard lattice equals the simplicial comass of the corresponding cohomology class; the lattice is the one supplied by the refined shortest-vector hardness result the paper cites as Theorem 4.4. Finally, the passage from complexes to manifolds is carried by maps $p:\\Sigma\\to X$ of $\\epsilon$-girth $\\delta$: $p$ is $\\epsilon$-dense in $X$ and the preimage of every $2\\epsilon$-ball has diameter at most $\\delta$, which is exactly the condition that lets Lipschitz maps from $\\Sigma$ extend to $X$ with controlled Lipschitz constant.","core_discovery":"The central discovery is Theorem 1.1: for every $n\\ge 2$, both $L_{\\neq 0}(\\Sigma)$ and $L_1(\\Sigma)$ are NP-hard to approximate within $N^{c/\\log\\log N}$, where $\\Sigma$ ranges over triangulated surfaces when $n=2$ or triangulations of $S^n$ when $n\\ge 3$, $N=\\operatorname{vol}\\Sigma$, and $c>0$ depends only on $n$. Since the hyperspherical radius is $1/L_{\\neq 0}(\\Sigma)$, this is the same as saying that hyperspherical radius cannot be approximated to within an almost-polynomial factor in polynomial time unless $P=NP$. The proof proceeds in two stages: it first establishes the same hardness for a relative constant $L_{\\neq 0}(X,h)$ on an $(n+1)$-dimensional simplicial complex $X$ with a distinguished homology class $h$, and then realizes $X$ metrically by a surface or a triangulated sphere $\\Sigma$ equipped with a small-girth map $p:\\Sigma\\to X$. The small-girth condition forces $L_{\\neq 0}(\\Sigma)$ and $L_1(\\Sigma)$ to track $L_{\\neq 0}(X,h)$ up to the desired factor, so the manifold statement inherits the hardness of the complex statement.","pith_inferences":["The transfer principle via small-girth maps is likely to apply to other metric invariants the paper mentions, such as Uryson widths or minimax volumes, whenever the invariant has a cohomological norm that can be approximated by linear programming.","Because the reduction uses only the structural form of the lattice hardness, a stronger shortest-vector inapproximability result would immediately yield a larger hardness factor for hyperspherical radius through the same chain.","One testable extension is to replace the $\\ell^\\infty$ norm in the lattice encoding with an $\\ell^p$ norm; if the comass-to-lattice matching survives, the same construction would give hardness of approximation for a family of mass-type invariants indexed by $p$.","The construction suggests that the computational hardness of hyperspherical radius is combinatorial: the metric is the fixed equilateral simplexwise metric, and all the difficulty enters through the triangulation's topology, not through curvature or metric fine structure."],"forward_implications":["If Theorem 1.1 is correct, no polynomial-time algorithm can approximate the hyperspherical radius of a general triangulated manifold to within any factor as large as $N^{c/\\log\\log N}$, unless $P=NP$.","The hardness holds on restricted input classes: triangulated surfaces of arbitrary genus for $n=2$ and triangulations of $S^n$ for $n\\ge 3$, so it is not caused by wild higher-dimensional topology.","Because the appendix gives an NP algorithm that outputs $L_{\\neq 0}(\\Sigma)$ and $L_1(\\Sigma)$ up to a constant factor, the almost-polynomial gap is essentially the strongest inapproximability factor that can be derived from an NP-hardness assumption alone.","The same reduction turns any future improvement in the cited lattice hardness into a stronger inapproximability factor for hyperspherical radius, since the geometric part of the construction is independent of the gap size.","The constructed manifolds form a family of certified hard instances: their Lipschitz constants are controlled by the $\\ell^\\infty$ shortest-vector problem, so they can serve as explicit benchmarks for algorithms that attempt to estimate metric invariants."],"supporting_citations":[{"why":"Supplies the NP-hardness of approximating the $\\ell^\\infty$ shortest vector in a lattice, including the refined 0/1-vector gap statement used as the starting reduction.","marker":"[5]"},{"why":"Provides the quantitative null-cobordism result used in Theorem 2.1 to control Lipschitz constants when extending maps across higher-dimensional cells.","marker":"[3]"},{"why":"Gives the polynomial-time constant-factor algorithm for triangulated 2-spheres that contrasts with the new hardness, and supplies the high-genus surface imitation construction for $n=2$.","marker":"[14]"},{"why":"States the shadowing principle in quantitative homotopy theory of which Theorem 2.1 is a corollary, anchoring the main Lipschitz-comass comparison.","marker":"[18]"},{"why":"Provides the asymptotic construction of small-girth maps from spheres to complexes that the $n\\ge 3$ proof turns into a polynomial-size simplicial approximation.","marker":"[9]"},{"why":"Supplies edgewise subdivision, used to control the sizes of subdivided complexes in the algorithmic simplicial versions of the geometric constructions.","marker":"[8]"},{"why":"Supplies the polynomial-time check that two maps are homotopic, which makes the NP certificate in the appendix valid.","marker":"[10]"}],"fun_headline_variants":["Hyperspherical radius approximation is NP-hard","NP-hard to approximate hyperspherical radius","Triangulated manifold radius NP-hard to approximate","Approximating hyperspherical radius is NP-hard","Hyperspherical radius: NP-hard to approximate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the strengthened shortest-vector hardness statement the paper imports from the cited shortest-vector paper (its Theorem 4.4): a hard lattice must have a shortest vector of the special form $u_0 + \\sum_j a_j u_j$ with coefficients $a_j\\in\\{0,1\\}$ and norm 1, while every other nonzero lattice vector has norm at least $N^{C/\\log\\log N}$; the paper says this follows by inspecting the cited proof but does not reproduce the verification.","fun_headline_variants_meta":{"raw":{"variants":["Hyperspherical radius approximation is NP-hard","NP-hard to approximate hyperspherical radius","Triangulated manifold radius NP-hard to approximate","Approximating hyperspherical radius is NP-hard","Hyperspherical radius: NP-hard to approximate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000811,"raw_usage":{"total_tokens":3501,"prompt_tokens":835,"completion_tokens":2666,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":451,"completion_tokens_details":{"reasoning_tokens":2594}},"tokens_in":451,"tokens_out":2666,"duration_ms":21354,"temperature":1.0,"reasoning_tokens":2594,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:34:03.550980+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Examine the cited shortest-vector proof to verify Theorem 4.4, or run the reduction on small SAT instances and search for a violation: a lattice where the shortest vector of the required 0/1 form has norm greater than 1, or where some other nonzero vector has norm below $N^{C/\\log\\log N}$. Either finding would break the chain from lattice hardness to $L_{\\neq 0}(X,h)$ and hence to Theorem 1.1.","supporting_citations":[{"cited_title":"Dinur, Approximating SVP∞ to within almost-polynomial factors is NP- hard, Theoret","cited_arxiv_id":null,"evidence_quote":"Supplies the NP-hardness of approximating the $\\ell^\\infty$ shortest vector in a lattice, including the refined 0/1-vector gap statement used as the starting reduction."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the quantitative null-cobordism result used in Theorem 2.1 to control Lipschitz constants when extending maps across higher-dimensional cells."},{"cited_title":"Guth, Lipshitz maps from surfaces , Geometric & Functional Analysis (GAF A)15 (2005), no","cited_arxiv_id":null,"evidence_quote":"Gives the polynomial-time constant-factor algorithm for triangulated 2-spheres that contrasts with the new hardness, and supplies the high-genus surface imitation construction for $n=2$."},{"cited_title":"Manin, Plato’s cave and differential forms , Geometry & Topology 23 (2019), no","cited_arxiv_id":null,"evidence_quote":"States the shadowing principle in quantitative homotopy theory of which Theorem 2.1 is a corollary, anchoring the main Lipschitz-comass comparison."},{"cited_title":"Ferry and B","cited_arxiv_id":null,"evidence_quote":"Provides the asymptotic construction of small-girth maps from spheres to complexes that the $n\\ge 3$ proof turns into a polynomial-size simplicial approximation."},{"cited_title":"Edelsbrunner and D","cited_arxiv_id":null,"evidence_quote":"Supplies edgewise subdivision, used to control the sizes of subdivided complexes in the algorithmic simplicial versions of the geometric constructions."},{"cited_title":"Filakovsk´ y and L","cited_arxiv_id":null,"evidence_quote":"Supplies the polynomial-time check that two maps are homotopic, which makes the NP certificate in the appendix valid."}],"review_version":1}