{"id":"911a3e2f-c8bd-4cd3-bc5a-49d7515ed7b0","arxiv_id":"1908.08384","paper_version":3,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For p at least 2, approximate closest vector search in ell_p norms becomes 2^O(n) (1/epsilon)^(n/2), and for 1<=p<=2 it becomes 2^O(n) (1/epsilon)^(n/p), via a new covering bound from the modulus of smoothness.","lead":"This paper gives faster algorithms for approximating the closest vector problem under ell_p norms, improving the running time from a (1/epsilon)^n dependence to (1/epsilon)^(n/2) when p is at least 2. The improvement comes from measuring how many convex pieces are needed to cover a norm ball, using the modulus of smoothness from Banach space theory.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No load-bearing defect in the CVP/covering upper bounds; the only concrete flaw is a noncentral spherical-measure overestimate in the Euclidean lower-bound proof.","rationale":"The reader identified the monotonicity fact behind Theorem 3.2 as the weakest assumption. I agree that this fact is the least familiar input, but it is a standard and correct theorem for normed planes, and the way it is used in the inclusion (2) is legitimate. The algorithmically load-bearing results are the upper bounds on (2,ε)-covering numbers and their conversion into CVP running times; these are self-contained apart from standard cited tools such as [DK16] and the modulus-of-smoothness estimates of [Lin63]. I checked the local-covering probability in Theorem 4.5, the binary-search boosting in Theorem 4.2, and the sparsifier-based route in Lemma 5.2 and Theorem 5.5; I did not find a gap that would invalidate the claimed running times. The one definite mathematical slip is in Theorem 2.7, where the surface measure of a spherical cap of radius sqrt(ε) is incorrectly bounded by ε^{n/2} instead of ε^{(n-1)/2}. This is a genuine error in a stated theorem, but the theorem is a supporting lower bound and is not used to prove the main upper bounds or the CVP algorithms. Therefore my read does not change the reader's ACCEPT verdict, though a revised version should correct or relativize the lower-bound claim.","tokens_in":16356,"tokens_out":57555,"duration_ms":567864,"concrete_test":"Recompute the spherical measure in Theorem 2.7 by integrating the cap {x ∈ S^{n-1} : ||x - p|| ≤ sqrt(5ε)}. For n=2 and ε=10^{-4}, the uniform measure is approximately 2 sqrt(5ε) ≈ 0.0447, whereas the claimed bound 2^{O(n)} ε^{n/2} is on the order of 10^{-4}/2^{O(1)}; the inequality fails. Repeat for general n and replace the exponent by (n-1)/2 to see whether the stated lower-bound claim still follows.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I do not find a load-bearing flaw in the central claim. The proof of Theorem 3.2 rests on the classical monotonicity fact [MSW01, Proposition 31], which is a valid property of normed planes, and the subsequent covering-to-CVP chain in Theorems 4.2, 4.6, and 5.5 is coherent. The supporting lower bound, however, contains a concrete measure error. In Theorem 2.7 the text infers from 'Qi ∩ S^{n-1} is contained in a cap of radius sqrt(5ε)' that σ(Qi ∩ S^{n-1}) ≤ 2^{O(n)} ε^{n/2}. A spherical cap of Euclidean radius r on S^{n-1} has uniform surface measure Θ_n(r^{n-1}), so the correct bound is O(ε^{(n-1)/2}), which is much larger than ε^{n/2} for small ε. Consequently the proof as written yields only a weaker lower bound than the stated Ω(2^{-O(n)}(1/ε)^{n/2}). This does not affect the algorithmic upper bounds or the validity of the (2,ε)-covering constructions, so the central claim survives.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies (2,ε)-coverings of convex bodies: collections of convex bodies whose union contains a given body K and whose doubles about their centroids are contained in (1+ε)K. Its main contribution is to bound the size of such coverings via the modulus of smoothness of K, yielding covering numbers 2^{O(n)} log(1/ε)(C/ε)^{n/q} for bodies with ρ(τ) ≤ Cτ^q. For ℓ_p balls this gives 2^{O(n)} log(1/ε)(1/ε)^{n/2} for p≥2 and 2^{O(n)} log(1/ε)(1/ε)^{n/p} for 1≤p≤2. The paper then shows how such coverings boost any constant-factor approximate CVP solver to a (1+ε)-approximate solver, with randomized and deterministic local-covering variants, and gives a separate sparsification-based algorithm with the same improved dependence on ε. It also treats polyhedral and zonotopal norms with O(n) facets/generators, and claims a matching lower bound for the Euclidean ball.","tokens_in":16550,"tokens_out":31540,"duration_ms":314885,"significance":"If correct, the main algorithmic results give a substantial improvement over the previous best general-norm CVP dependence of 2^{O(n)}(1/ε)^n: for fixed ℓ_p with p≥2 the ε-dependence drops to (1/ε)^{n/2}, and for 1≤p≤2 to (1/ε)^{n/p}, with space depending only on the underlying constant-factor solver plus 2^n poly(n) space in the sparsification variant. The modulus-of-smoothness technique is elegant: it derives purely geometric covering bounds that are then converted, in a black-box way, into CVP algorithms, and the connection to lattice sparsification in Section 5 is a genuinely new and interesting observation. The paper also provides explicit deterministic coverings for zonotopes and centrally symmetric polytopes with polynomially many facets, generalizing the earlier ℓ∞ result. The central algorithmic claims are coherent and the proofs build on clearly cited external theorems. However, as detailed below, the lower-bound theorem for the Euclidean ball is not proved by the argument given; this does not undermine the upper-bound algorithms but does invalidate the claimed tightness of the covering bound.","major_comments":[{"comment":"The proof of the lower bound contains a measure error that invalidates the stated conclusion. The text infers from the fact that Qi∩S^{n-1} is contained in a spherical cap of Euclidean radius sqrt(5ε) that σ(Qi∩S^{n-1}) ≤ 2^{O(n)} ε^{n/2}. However, a spherical cap of Euclidean radius r on S^{n-1} has uniform surface measure Θ_n(r^{n-1}), so the correct upper bound is 2^{O(n)} ε^{(n-1)/2}. Consequently the argument as written only yields N ≥ 2^{-O(n)}(1/ε)^{(n-1)/2}, which is weaker by a factor ε^{-1/2} than the claimed Ω(2^{-O(n)}(1/ε)^{n/2}). The claimed matching lower bound for the Euclidean unit ball is therefore not established. Since this lower bound is not used in the CVP algorithms of Sections 4 and 5, the algorithmic upper bounds are unaffected; nevertheless, the paper's assertion in Section 1 that the upper bound 'matches' the lower bound needs either a repaired proof or a weakened statement.","section":"Theorem 2.7"}],"minor_comments":[{"comment":"The statement 'consists of at least Op(2^{-O(n)}(1/ε)^{n/2}) convex bodies' mixes O-notation into a lower bound; it should be phrased as Ω(2^{-O(n)}(1/ε)^{n/2}).","section":"Theorem 2.7"},{"comment":"Theorem 3.2 assumes q > 1, but Corollary 3.4 includes the case p = 1, for which the modulus bound gives q = 1 and the term O(C)^{n/(q-1)} is undefined. The ℓ_1 bound is of course already covered by the trivial Lemma 2.2, but the paper should state this explicitly or adjust the theorem's hypotheses.","section":"Theorem 3.2 / Corollary 3.4"},{"comment":"The running time expression contains the term O(C)^{n/(q-1)}, which is again undefined for q=1; the same remark as above applies if the theorem is meant to cover ℓ_1.","section":"Theorem 4.6"}],"recommendation":"major_revision","confidential_remarks":"The paper's core algorithmic results are strong and, as far as I can tell, correct. The only serious flaw is the proof of the Euclidean lower bound in Theorem 2.7, which is a non-algorithmic but stated contribution and is used to claim that the ℓ_2 covering bound is tight up to log factors. If the authors can repair the proof or explicitly weaken the theorem and adjust the 'matching' language, I would support publication. I also checked the cited geometric monotonicity fact [MSW01, Proposition 31] used in Theorem 3.2; it is a valid classical fact about normed planes, so I do not share the concern that the main covering proof is circular."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about this paper.\n\nThe main machinery is sound and worth your time. Naszódi and Venzin connect the classical modulus of smoothness of a norm to the (2,ε)-covering numbers that Eisenbrand et al. introduced for CVP, and that gives real improvements in the (1/ε) dependence for ℓ_p norms: (1/ε)^{n/2} for p ≥ 2 and (1/ε)^{n/p} for 1 ≤ p ≤ 2, beating the (1/ε)^n of Dadush–Kun. The boosting theorem (4.2), the local-covering randomized version (4.6), and the sparsification connection (Lemma 5.2) all check out. The sparsification observation is the nicest surprise: the modulus of smoothness shows up naturally in the sparsifier analysis, and it gives a clean alternative route to the same running time.\n\nNow the soft spots, in proportion. The Euclidean lower bound (Theorem 2.7) has a real measure error. The proof claims that Q_i ∩ S^{n-1} lying in a cap of radius √(5ε) gives σ(Q_i ∩ S^{n-1}) ≤ 2^{O(n)} ε^{n/2}. That's wrong: a spherical cap of Euclidean radius r on S^{n-1} has measure Θ(r^{n-1}), so the correct bound is 2^{O(n)} ε^{(n-1)/2}, and the stated Ω(2^{-O(n)} ε^{-n/2}) does not follow — you only get ε^{-(n-1)/2}. This does not affect the upper bounds or the CVP algorithms, which never rely on it, but the claim that the smoothness bound \"matches the lower bound\" for the Euclidean ball needs a caveat until the proof is repaired.\n\nSmaller issues: the key geometric inclusion (2) in Theorem 3.2 is compressed; it rests on a classical monotonicity fact about normed planes ([MSW01, Prop. 31]) that is valid, per my check, but the application deserves more detail. The paper also has minor slips — O-notation inside the lower bound, and a typo in Theorem 3.3's second estimate.\n\nThe paper is for people working on approximate lattice problems and covering arguments in geometry of numbers. The central ideas are new, the main proofs hold up, and the flaw I found is peripheral and fixable by weakening the statement. Deserves a serious referee; I'd send it to review and tell the referee to check Theorem 2.7 and the normed-plane fact in Theorem 3.2 carefully.","headline":"The modulus-of-smoothness route to (2,ε)-coverings is genuine and improves ℓ_p CVP to (1/ε)^{n/2} or (1/ε)^{n/p}; the Euclidean lower bound has a spherical-cap measure error, but that's peripheral to the main claims.","tokens_in":17120,"tokens_out":13984,"would_cite":true,"duration_ms":118306,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["52C17","52A20","11H06","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the modulus of smoothness of a symmetric convex body controls its $(2,\\varepsilon)$-covering number, yielding faster $(1+\\varepsilon)$-approximate closest-vector algorithms for $\\ell_p$ norms and for polytopes and…","keywords":["closest vector problem","(2,epsilon)-covering","covering number","modulus of smoothness","ell_p norms","lattice sparsification","convex bodies","zonotopes"],"falsifier":"Compute, for the unit ball of a regular hexagon, the norm-distance from a vertex $p$ to points moving along the boundary toward $-p$: if that distance ever strictly decreases along the arc, the monotonicity fact used in the proof of Theorem 3.2 is false. Alternatively, for a fixed small $\\varepsilon$ and low dimension $n=3$ or $n=4$, count the minimal number of convex pieces in a $(2,\\varepsilon)$-covering of the Euclidean ball: a rate consistently smaller than $(1/\\varepsilon)^{n/2}$ would contradict the claimed lower-bound/upper-bound match, while a larger rate would refute Theorem 3.2's exponent for $q=2$.","tokens_in":16136,"feed_emoji":"🎯","tokens_out":11219,"duration_ms":90569,"temperature":0.7,"pith_summary":"The paper sets out to speed up the $(1+\\varepsilon)$-approximate Closest Vector Problem (CVP) for $\\ell_p$ norms, whose previous best general-norm running time was $2^{O(n)}(1/\\varepsilon)^n$. Its route is a geometric counting problem: how many convex pieces are needed to cover a norm ball so that each piece, doubled about its centroid, stays inside a $(1+\\varepsilon)$-dilation of the ball. The paper proves that a bound on the modulus of smoothness of the ball---how well its boundary is approximated by hyperplanes---controls this covering number, giving $2^{O(n)}(1/\\varepsilon)^{n/2}$ pieces for $p\\ge 2$ and $2^{O(n)}(1/\\varepsilon)^{n/p}$ for $1\\le p\\le 2$. Feeding such coverings into a binary-search boosting scheme turns any constant-factor CVP solver into a $(1+\\varepsilon)$-approximate solver with those improved running times. A separate result ties the same smoothness modulus to lattice sparsification, yielding an alternative solver with the same improved $\\varepsilon$-dependence and polynomial space.","feed_headline":"Smoothness halves the epsilon exponent in closest-vector search","feed_subtitle":"A convex body's local flatness governs how many pieces cover it, and that number controls (1+epsilon)-approximate closest-vector algorithms.","key_machinery":"The load-bearing objects are the $(2,\\varepsilon)$-covering number and the modulus of smoothness. A $(2,\\varepsilon)$-covering of $K$ is a family of convex bodies $Q_i$ whose union contains $K$ and whose double homothets, obtained by scaling each $Q_i$ by factor two about its centroid, all lie inside $(1+\\varepsilon)K$. The modulus of smoothness, $\\rho_K(\\tau)=\\frac{1}{2}\\sup_{\\|x\\|_K=\\|y\\|_K=1}(\\|x+\\tau y\\|_K+\\|x-\\tau y\\|_K-2)$, measures how well the boundary is locally approximated by supporting hyperplanes: a bound $C\\tau^q$ means points within distance $\\tau$ of a boundary point sit within $O(\\tau^q)$ of the tangent hyperplane. The proof of Theorem 3.2 uses that smoothness to show a local inclusion of the boundary near a point $p$ inside the cone $\\operatorname{conv}(0,B_p)$ over a small cap $B_p$, then slices the circumscribed cylinder into $O(\\log(1/\\varepsilon))$ pieces whose doubles remain inside $(1+\\varepsilon)K$. This local construction is repeated over a packing of the boundary, which costs $(C/\\varepsilon)^{n/q}$ points. The algorithmic half is a binary-search boosting scheme that, given any such covering, calls a 2-approximate CVP solver $N \\log(1/\\varepsilon)$ times and recovers a $(1+7\\varepsilon)$-approximate solution.","core_discovery":"On the paper's own terms, the central discovery is Theorem 3.2: if an origin-symmetric convex body $K$ has modulus of smoothness bounded by $C\\tau^q$, then $K$ admits a $(2,\\varepsilon)$-covering of size $2^{O(n)} \\log(1/\\varepsilon)(C/\\varepsilon)^{n/q}$, plus an additive $O(C)^{n/(q-1)}$ term when $\\varepsilon$ is not small. Since the $\\ell_p$ ball has modulus bounded by $O(\\tau^2)$ for $p\\ge 2$ and by $O(\\tau^p)$ for $1\\le p\\le 2$, the covering numbers become $2^{O(n)} \\log(1/\\varepsilon)(1/\\varepsilon)^{n/2}$ and $2^{O(n)} \\log(1/\\varepsilon)(1/\\varepsilon)^{n/p}$. Theorem 4.2 then shows that any $(2,\\varepsilon)$-covering boosts any 2-approximate CVP solver to a $(1+7\\varepsilon)$-approximate solver with $N \\log(1/\\varepsilon)$ calls, so the covering bounds translate directly into running times of $2^{O(n)}(1/\\varepsilon)^{n/2}$ and $2^{O(n)}(1/\\varepsilon)^{n/p}$ for $(1+\\varepsilon)$-CVP in $\\ell_p$. The same machinery gives deterministic $(1+\\varepsilon)$-CVP for centrally symmetric polytopes with $m$ facets and for zonotopes with $m$ generators in time $\\mathrm{poly}(n,b,1/\\varepsilon)\\,2^{O(n+m)} \\log(1/\\varepsilon)^m$. Finally, Lemma 5.2 observes that a $(K,\\varepsilon^{1/q})$-sparsifier preserves distances up to an additive $2C\\varepsilon$, which plugs into enumeration to give a simpler sparsification-based algorithm with the same improved $\\varepsilon$-exponents and $2^n \\mathrm{poly}(n)$ space.","pith_inferences":["The abstract Theorem 3.2 does not enumerate its own consequences: any family of norms with a known modulus-of-smoothness bound, such as Schatten norms or uniformly smooth spaces, would inherit a $(1+\\varepsilon)$-CVP algorithm whose $\\varepsilon$-exponent is $n/q$, so the framework could be tested well beyond $\\ell_p$.","The paper's lower bound for the Euclidean ball suggests that the exponent $n/2$ is intrinsic for Hilbertian norms; a matching lower-bound construction for $1\\le p\\le 2$, if it exists, would confirm that the $n/p$ exponent cannot be improved by any other covering scheme.","Lemma 5.2 links smoothness to sparsification in a way the paper uses only for CVP; the same observation is likely to transfer to other enumerative lattice algorithms, such as shortest-vector search or integer programming, where enumeration cost is controlled by $G(K,L)$.","Because the local covering in Theorem 4.5 can be generated by sampling, the randomized algorithm's space remains that of the 2-CVP solver; one concrete extension is to plug in a different constant-factor solver and compare the resulting space-time tradeoff for small $\\varepsilon$."],"forward_implications":["For every fixed $p\\ge 2$, $(1+\\varepsilon)$-approximate CVP in $\\ell_p$ can be solved in time $2^{O(n)}(1/\\varepsilon)^{n/2}$, and for $1\\le p\\le 2$ in time $2^{O(n)}(1/\\varepsilon)^{n/p}$, improving the previous general-norm bound $2^{O(n)}(1/\\varepsilon)^n$.","Any 2-approximate CVP solver for general norms can be boosted to a $(1+\\varepsilon)$-approximate solver using only $N \\log(1/\\varepsilon)$ calls, where $N$ is the $(2,\\varepsilon)$-covering number, so improvements in covering numbers translate directly into improvements in running time.","For centrally symmetric polytopes with $m$ facets and for zonotopes generated by $m$ segments, $(1+\\varepsilon)$-CVP is solvable deterministically in time $\\mathrm{poly}(n,b,1/\\varepsilon)\\,2^{O(n+m)} \\log(1/\\varepsilon)^m$.","A lattice sparsifier of parameter $\\varepsilon^{1/q}$ preserves distances to the target up to an additive $2C\\varepsilon$ for a body with modulus of smoothness $C\\tau^q$, so enumeration after sparsification yields a $(1+\\varepsilon)$-CVP solver with the same improved $\\varepsilon$-exponents and $2^n \\mathrm{poly}(n)$ space.","The Euclidean ball admits no $(2,\\varepsilon)$-covering with fewer than $2^{-O(n)}(1/\\varepsilon)^{n/2}$ bodies, so for $p=2$ the covering exponent obtained from smoothness is optimal up to constants and logarithmic factors."],"supporting_citations":[{"why":"Supplies the general-norm baseline, the 2-approximate CVP solver that the boosting theorems call, and the lattice-sparsification and enumeration machinery used in Section 5.","marker":"[DK16]"},{"why":"Introduces the covering-based boosting scheme for CVP and the cube-covering construction that the polytope and zonotope coverings generalize.","marker":"[EHN11]"},{"why":"Provides the modulus-of-smoothness estimates for $\\ell_p$ balls that convert Theorem 3.2 into the concrete covering numbers of Corollary 3.4.","marker":"[Lin63]"},{"why":"Supplies Proposition 31, the monotonicity of norm-distance along the unit circle in normed planes, which justifies the local boundary inclusion in the proof of Theorem 3.2.","marker":"[MSW01]"},{"why":"Provides the deterministic polynomial-space epsilon-net construction that derandomizes the local covering step in Theorem 4.6.","marker":"[Dad13]"},{"why":"Supplies the lattice-enumeration routine used with the sparsifier in the Section 5 alternative CVP algorithm.","marker":"[DPV11]"}],"fun_headline_variants":["Smoothness cuts epsilon exponent in closest-vector search","New covering bounds halve CVP epsilon exponent","Closest-vector search sped by convex body smoothness","Epsilon exponent reduced for ell_p closest-vector algorithms","Smoothness boosts approximate CVP via better coverings"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the main covering bound depends on a classical monotonicity fact in two-dimensional normed planes---that on the unit circle, the norm-distance from a fixed boundary point $p$ to a moving point never decreases as the moving point travels from $p$ to $-p$---and if that fact fails in the stated generality, the local inclusion that starts the covering argument, and with it the improved CVP running times, would not follow.","fun_headline_variants_meta":{"raw":{"variants":["Smoothness cuts epsilon exponent in closest-vector search","New covering bounds halve CVP epsilon exponent","Closest-vector search sped by convex body smoothness","Epsilon exponent reduced for ell_p closest-vector algorithms","Smoothness boosts approximate CVP via better coverings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001279,"raw_usage":{"total_tokens":5458,"prompt_tokens":1402,"completion_tokens":4056,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":1018,"completion_tokens_details":{"reasoning_tokens":3977}},"tokens_in":1018,"tokens_out":4056,"duration_ms":92595,"temperature":1.0,"reasoning_tokens":3977,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:42:29.176877+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, for the unit ball of a regular hexagon, the norm-distance from a vertex $p$ to points moving along the boundary toward $-p$: if that distance ever strictly decreases along the arc, the monotonicity fact used in the proof of Theorem 3.2 is false. Alternatively, for a fixed small $\\varepsilon$ and low dimension $n=3$ or $n=4$, count the minimal number of convex pieces in a $(2,\\varepsilon)$-covering of the Euclidean ball: a rate consistently smaller than $(1/\\varepsilon)^{n/2}$ would contradict the claimed lower-bound/upper-bound match, while a larger rate would refute Theorem 3.2's exponent for $q=2$.","supporting_citations":[],"review_version":1}