REVIEW 1 major objections 3 minor 22 references
Covering convex bodies and the Closest Vector Problem
T0 review · 1 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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…
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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$.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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$.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [Theorem 2.7] 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.
minor comments (3)
- [Theorem 2.7] 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}).
- [Theorem 3.2 / Corollary 3.4] 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.
- [Theorem 4.6] 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.
Circularity Check
No self-citation or fitted-input circularity; the central covering and CVP results are derived from independent geometric and algorithmic ingredients.
full rationale
I found no circular step in the derivation chain. Theorem 3.2 takes the modulus-of-smoothness bound ρ_K(τ) ≤ Cτ^q as an independent quantitative hypothesis and derives a (2,ε)-covering bound from it; the proof uses the definition of the modulus, the classical monotonicity result for normed planes cited as [MSW01, Proposition 31], and packing arguments such as Lemma 2.2. None of these inputs is the covering statement being proved, and no fitted constant is later renamed as a prediction. Corollary 3.4 is obtained by substituting Lindenstrauss's published estimates for the ℓ_p modulus of smoothness, which are external classical results, not assumptions tailored to the desired covering exponent. The CVP algorithms in Theorems 4.2, 4.6 and 5.5 reduce to external approximate-CVP, sparsification, enumeration, and epsilon-net constructions ([DK16], [DPV11], [Dad13]); the running times are obtained by counting calls to those subroutines and by the covering bounds, not by assuming the final running time. The paper contains no self-citations at all: the reference list contains no work by Naszódi or Venzin, so the self-citation patterns do not arise. The only concrete defect visible in the text is non-circular: in Theorem 2.7 the inference from 'Q_i ∩ S^{n-1} is contained in a cap of radius sqrt(5ε)' to σ(Q_i ∩ S^{n-1}) ≤ 2^{O(n)} ε^{n/2} is quantitatively wrong, since a spherical cap of Euclidean radius r has measure of order r^{n-1}, giving only O(ε^{(n-1)/2}). This would weaken the stated lower bound, but it does not feed back into the covering upper bounds or the CVP algorithms, which are the central claims. Accordingly, the overall circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math Classical monotonicity fact in normed planes: distance to p increases along the unit circle from p to -p [MSW01, Proposition 31].
- standard math Lindenstrauss modulus of smoothness bounds for ell_p: rho_{l_p}(tau) <= 2 tau^2 for p>=2 and <= tau^p/p for 1<=p<=2.
- standard math Dadush-Kun theorem: deterministic (1+epsilon)-CVP for any norm in 2^O(n)(1+1/epsilon)^n time and 2^n poly(n,b) space.
- standard math Lattice sparsifier and lattice enumeration algorithms with stated time and space bounds [DK16, DPV11].
- standard math Milman-Pajor centroid inequality: vol(Q intersect -Q) >= 2^-n vol(Q) for a convex body Q with centroid at the origin.
Cite this review
Pith. "Pith review of Covering convex bodies and the Closest Vector Problem." pith.science (2026). https://pith.science/paper/E6YOTMWH
@misc{pith2026190808384,
author = {Pith},
title = {Pith review of: Covering convex bodies and the Closest Vector Problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/E6YOTMWH}},
note = {Machine review of arXiv:1908.08384}
}
abstract
We present algorithms for the $(1+\epsilon)$-approximate version of the closest vector problem for certain norms. The currently fastest algorithm (Dadush and Kun 2016) for general norms has running time of $2^{O(n)} (1/\epsilon)^n$. We improve this substantially in the following two cases. For $\ell_p$-norms with $p>2$ (resp. $p \in [1,2]$) fixed, we present an algorithm with a running time of $2^{O(n)} (1/\epsilon)^{n/2}$ (resp. $2^{O(n)} (1/\epsilon)^{n/p}$). This result is based on a geometric covering problem, that was introduced in the context of CVP by Eisenbrand et al.: How many convex bodies are needed to cover the ball of the norm such that, if scaled by two around their centroids, each one is contained in the $(1+\epsilon)$-scaled homothet of the norm ball? We provide upper bounds for this problem by exploiting the \emph{modulus of smoothness} of the $\ell_p$-balls. Applying a covering scheme, we can boost any constant approximation algorithm for CVP to a $(1+\epsilon)$-approximation algorithm with the improved run time, either using a straightforward sampling routine or using the deterministic algorithm of Dadush for the construction of an epsilon net. The space requirement only depends on the constant approximation CVP solver used. Furthermore, we generalise the result of Eisenbrand et al. for the $\ell_\infty$-norm. For centrally symmetric polytopes (resp. zonotopes) with $O(n)$ facets (resp. generated by $O(n)$ line segments), we provide a deterministic $O(\log_2(1/\epsilon))^{O(n)}$ time algorithm. Finally, we establish a connection between the \emph{modulus of smoothness} and \emph{lattice sparsification}. Using the enumeration and sparsification tools developped by Dadush, Kun, Peikert and Vempala, this leads to a simple alternative to the boosting procedure for CVP under $\ell_p$-norms. This connection might be of independent interest.
Figures
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
Probabilistic Checking of Proofs and Hardness of Approximation Problems
Sanjeev Arora. Probabilistic Checking of Proofs and Hardness of Approximation Problems . PhD thesis, Berkeley, CA, USA, 1995. UMI Order No. GAX95-30468
work page 1995
-
[4]
Just take the average! A n embarrassingly simple 2 \^ n-time algorithm for SVP (and CVP)
Divesh Aggarwal and Noah Stephens - Davidowitz. Just take the average! A n embarrassingly simple 2 \^ n-time algorithm for SVP (and CVP) . In 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7-10, 2018, New Orleans, LA, USA , pages 12:1--12:19, 2018
work page 2018
-
[5]
Sampling methods for shortest vectors, closest vectors and successive minima
Johannes Bl \" o mer and Stefanie Naewe. Sampling methods for shortest vectors, closest vectors and successive minima. Theor. Comput. Sci. , 410(18):1648--1665, 2009
work page 2009
-
[6]
A o(1/ \( \) 2) n -- time sieving algorithm for approximate integer programming
Daniel Dadush. A o(1/ \( \) 2) n -- time sieving algorithm for approximate integer programming. In LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings , pages 207--218, 2012
work page 2012
-
[7]
A Deterministic Polynomial Space Construction for eps-nets under any Norm
Daniel Dadush. A deterministic polynomial space construction for eps-nets under any norm, 2013. ArXiv:1311.6671
work page Pith review arXiv 2013
-
[8]
Dyer, Alan M
Martin E. Dyer, Alan M. Frieze, and Ravi Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. J. ACM , 38(1):1--17, 1991
1991
Show all 22 references
-
[9]
Lattice sparsification and the approximate closest vector problem
Daniel Dadush and G \' a bor Kun. Lattice sparsification and the approximate closest vector problem. Theory of Computing , 12(1):1--34, 2016
2016
-
[10]
Approximating CVP to within almost-polynomial factors is NP -hard
Irit Dinur, Guy Kindler, Ran Raz, and Shmuel Safra. Approximating CVP to within almost-polynomial factors is NP -hard. Combinatorica , 23(2):205--243, 2003
2003
-
[11]
Enumerative lattice algorithms in any norm via m-ellipsoid coverings
Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in any norm via m-ellipsoid coverings. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on Foundations of Computer Science , FOCS '11, pages 580--589, Washington, DC, USA, 2011. IEEE Compute...
2011
-
[12]
Covering cubes and the closest vector problem
Friedrich Eisenbrand, Nicolai H \" a hnle, and Martin Niemeier. Covering cubes and the closest vector problem. In Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011 , pages 417--423, 2011
2011
-
[13]
Geometric Algorithms and Combinatorial Optimization , volume 40
Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric Algorithms and Combinatorial Optimization , volume 40. The Journal of the Operational Research Society, 01 1988
1988
-
[14]
On compact representations of voronoi cells of lattices
Christoph Hunkenschr \" o der, Gina Reuland, and Matthias Schymura. On compact representations of voronoi cells of lattices. In Integer Programming and Combinatorial Optimization - 20th International Conference, IPCO 2019, Ann Arbor, MI, USA, May 22-24, 2019, Proceedings , pag...
2019
-
[15]
Minkowski's convex body theorem and integer programming
Ravi Kannan. Minkowski's convex body theorem and integer programming. Math. Oper. Res. , 12(3):415--440, 1987
1987
-
[16]
Hendrik W. Lenstra. Integer programming with a fixed number of variables. Math. Oper. Res. , 8(4):538--548, 1983
1983
-
[17]
On the modulus of smoothness and divergent series in banach spaces
Joram Lindenstrauss. On the modulus of smoothness and divergent series in banach spaces. Michigan Math. J. , 10(3):241--252, 08 1963
1963
-
[18]
Entropy and asymptotic geometry of non-symmetric convex bodies
Vitali Milman and Alain Pajor . Entropy and asymptotic geometry of non-symmetric convex bodies. Adv. Math. , 152(2):314--335, 2000
2000
-
[19]
Swanepoel, and Gunter Wei
Horst Martini, Konrad J. Swanepoel, and Gunter Wei . The geometry of M inkowski spaces---a survey. I . Expo. Math. , 19(2):97--142, 2001
2001
-
[20]
A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations
Daniele Micciancio and Panagiotis Voulgaris. A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010...
2010
-
[21]
Approximating the centroid is hard
Luis Rademacher. Approximating the centroid is hard. In Proceedings of the 23rd ACM Symposium on Computational Geometry, Gyeongju, South Korea, June 6-8, 2007 , pages 302--305, 2007
2007
-
[22]
van Emde Boas
P. van Emde Boas. Another NP -complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam , 1981
1981
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.