TL;DR
This paper investigates the geometric and combinatorial properties of Voronoi cells for lattices under arbitrary norms. The authors show that for "nice" norms (strictly convex and smooth), the Voronoi cells retain a familiar structure related to "Voronoi-relevant vectors." However, they also demonstrate that for more general norms, the complexity can explode, with lattices exhibiting an unbounded number of these critical vectors, which has significant implications for extending existing lattice algorithms.
What Problem Does This Paper Address?
The field of "geometry of numbers" deals with the interplay between lattices (discrete arrangements of points) and geometric objects like norms. A fundamental concept is the Voronoi cell, which for a lattice and a norm, is the set of points closer to the origin than to any other lattice point. While extensively studied for the standard Euclidean norm (l2-norm), the behavior of Voronoi cells under arbitrary norms (like lp-norms for p ≠ 2) is much less understood. This lack of understanding is a bottleneck for developing efficient algorithms for important computational problems like the Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) in these more general settings. Specifically, recent breakthroughs in solving SVP/CVP for Euclidean norms rely heavily on the fact that the number of "Voronoi-relevant vectors" (vectors that define the boundaries of the Voronoi cell) is bounded by a function of the lattice dimension only. The paper asks: does this hold for arbitrary norms?
Methods
The paper employs a combination of geometric analysis and constructive proofs.
- Geometric Characterization: They introduce and utilize the concepts of "Voronoi-relevant" and "weak Voronoi-relevant" vectors. They prove that for strictly convex and smooth norms, the Voronoi cell is precisely defined by the Voronoi-relevant vectors (Theorem 2). For general norms, a larger set, the weak Voronoi-relevant vectors, is needed (Theorem 3).
- Facet Analysis: The authors establish a connection between Voronoi-relevant vectors and the facets (boundary faces) of Voronoi cells. For strictly convex and smooth norms, they show a bijection between these two (Theorem 6).
- Constructive Proof for Complexity: The core negative result is achieved through a constructive approach. They build a specific family of 3D lattices and demonstrate that, for the l3-norm, these lattices can be constructed to have an arbitrarily large number of Voronoi-relevant vectors (Theorem 7). This construction involves carefully chosen rotations and scaling of a base lattice.
- Convex Geometry Tools: The proofs leverage tools from convex geometry, such as supporting hyperplanes, convex duality, and the Regular Level Set Theorem, to analyze the properties of norms and their associated unit balls.
Datasets
Not discussed in the paper. The paper deals with theoretical constructions of lattices and their properties, not empirical evaluation on datasets.
Key Insights and Ideas
- Norm Dictates Structure: The "niceness" of a norm (specifically, strict convexity and smoothness) significantly impacts the structure and complexity of Voronoi cells. "Nice" norms lead to more predictable and manageable Voronoi cells, similar to the Euclidean case.
- The "Voronoi-Relevant" Vector Bottleneck: The number of Voronoi-relevant vectors is a critical parameter. If this number is bounded by the dimension, algorithms like Micciancio-Voulgaris can achieve single exponential time. The paper shows this bound breaks down for general norms.
- Complexity Explosion: The construction of lattices with an unbounded number of Voronoi-relevant vectors for the l3-norm is a striking result. It implies that a direct generalization of efficient Euclidean-norm algorithms to arbitrary lp-norms (for p > 2) is unlikely without losing the single exponential time complexity.
- Two Dimensions are "Easier": For 2D lattices and strictly convex norms, the Voronoi cells behave much like their Euclidean counterparts, with a bounded number of facets. This suggests that dimensionality plays a crucial role in the complexity.
Key Results
- Theorem 2: For strictly convex and smooth norms, Voronoi cells are defined by Voronoi-relevant vectors.
- Theorem 3: For any norm, Voronoi cells are defined by weak Voronoi-relevant vectors.
- Theorem 6: For strictly convex and smooth norms, there's a bijection between Voronoi-relevant vectors and facets of the Voronoi cell.
- Theorem 7: A family of 3D lattices is constructed that, with respect to the l3-norm, has an arbitrarily large number of Voronoi-relevant vectors. This is the paper's main negative result regarding algorithmic generalization.
- Proposition 9: For 2D lattices and strictly convex norms, the number of Voronoi-relevant vectors is bounded (4 or 6).
Limitations and Future Work
- Smoothness Assumption: The proofs for the bijection between Voronoi-relevant vectors and facets (Theorem 6) and the manifold nature of bisector intersections (Proposition 20) rely on the norm being smooth. The authors note that this assumption is needed for their proof techniques in higher dimensions and pose it as an open question whether it can be omitted.
- Generalization to Other Norms: While the construction for unbounded Voronoi-relevant vectors is shown for the l3-norm, the authors suggest the ideas apply to all lp-norms for p > 2, with parameter adjustments. Explicitly proving this for all such norms would be a natural extension.
- Weak Voronoi-Relevant Vectors: The paper shows that weak Voronoi-relevant vectors are sufficient for describing Voronoi cells for any norm. However, it is an open question whether the number of weak Voronoi-relevant vectors can be bounded by a function of the dimension and covering radius/successive minima for all norms and lattices.
- Algorithmic Implications: While the paper shows limitations for exact algorithms, it acknowledges that these results can still inform approximate algorithms for CVP in general norms. Further research could explore how to best leverage these findings for practical approximate algorithms.
Summary updated