In the study of lattices—discrete grids of points in space—the most fundamental questions involve distance. The Shortest Vector Problem (SVP) asks for the lattice point closest to the origin, while the Closest Vector Problem (CVP) asks for the point closest to an arbitrary target. In a standard Euclidean world, these problems are governed by the geometry of the Voronoi cell: the region of space where a specific lattice point is the unique closest neighbor.
However, when we move beyond the Euclidean norm ($L_2$) to general norms ($L_p$ or arbitrary convex bodies), the geometric simplicity that researchers rely on begins to disintegrate. This transition triggers a "complexity explosion" that fundamentally alters the tractability of lattice algorithms.
The Geometry of the Explosion
In Euclidean space, the Voronoi cell of a lattice is a polytope with a manageable number of faces. These faces are defined by "Voronoi-relevant vectors"—a subset of lattice points that act as the cell's immediate neighbors. For a lattice in $n$ dimensions, the number of these vectors is bounded by $2(2^n - 1)$.
The landscape changes dramatically under non-Euclidean norms. Blömer and Kohn demonstrated that for general norms, the number of Voronoi-relevant vectors can become unbounded. They provided a constructive proof showing that even in just three dimensions, a lattice can be designed to have an arbitrarily large number of these critical vectors when measured under the $L_3$ norm.
This "explosion" means that algorithms designed to navigate the lattice by hopping between Voronoi neighbors lose their efficiency. As Blömer and Kohn argue, this represents a fundamental barrier to generalizing Euclidean lattice solvers to higher $L_p$ norms ($p > 2$).
Bridging the Gap with M-ellipsoids
To solve lattice problems in these "difficult" geometries, researchers have sought ways to approximate complex convex bodies with simpler ones. The primary tool for this is the M-ellipsoid, a geometric object that captures the essential shape of a convex body.
Dadush and Vempala introduced a breakthrough deterministic algorithm that constructs an approximate M-ellipsoid for any convex body. By solving a novel convex program, they were able to solve SVP under any norm in $O(\log n)^n$ time, a significant improvement over previous deterministic bounds.
Building on this, Dadush et al. used M-ellipsoid coverings to enumerate lattice points within arbitrary convex bodies. This approach allows for solving SVP and CVP in general norms by effectively "sandwiching" the complex target geometry between ellipsoids that are easier to compute. However, as Dadush and Vempala later noted, these deterministic CVP solutions often carry a "proximity constraint"—they work efficiently only when the target point is relatively close to the lattice.
The Limits of Approximation
Even with sophisticated geometric tools, the inherent hardness of these problems remains a steep wall. The difficulty isn't just a lack of clever algorithms; it is embedded in the complexity classes themselves.
- Fine-Grained Hardness: Eisenbrand and Venzin established that for $L_p$ norms where $p$ is not an even integer, CVP cannot be solved in $2^{(1-\epsilon)n}$ time unless the Strong Exponential Time Hypothesis (SETH) is false. This suggests that the Euclidean norm ($L_2$) is a rare island of relative efficiency.
- Parameterized Intractability: Even when the solution we are looking for is "short" (a small parameter $k$), the problem remains hard. Bhattacharyya et al. proved that $k$-SVP is fixed-parameter intractable for most $L_p$ norms, meaning we cannot isolate the exponential complexity to just the length of the vector.
- Preprocessing Limits: One might hope that by pre-calculating the lattice's structure (preprocessing), the query time for CVP could be reduced. However, Khot et al. showed that even with unlimited preprocessing, approximating CVP remains nearly as hard as the standard version, establishing a strong lower bound on what "cheating" with offline computation can achieve.
The $L_1$ Anomaly
Despite these broad results, the $L_1$ norm (Manhattan distance) remains a persistent mystery. While many $L_p$ norms have been proven hard, the $L_1$ norm often resists standard reduction techniques. Bhattacharyya et al. pointed out that reductions often produce irrational lattice bases, which are incompatible with the discrete requirements of $L_1$ complexity proofs. Consequently, as noted by Fomin et al., establishing the parameterized hardness of $L_1$-SVP remains one of the key open goals in the field.
Key Foundational Work
2log1-ε n hardness for the closest vector problem with preprocessing (2012) — contributed 3 concept elements to this direction.
Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings (2011) — contributed 2 concept elements to this direction.
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms (2012) — contributed 2 concept elements to this direction.