This paper gives an extremely detailed account of a greedy lattice reduction algorithm and its complexity analysis up to dimension four. It also studies failure of the algorithm starting at dimension five. For a general perspective on the closest vector problem (CVP) and shortest vector problem (SVP) associated to lattices, see Khot’s paper [1].
Nguyen and Stehl¿ work with Minkowski-reduced lattices. A d-dimensional lattice L is generated by a spanning set of vectors b1 , ... ,bd (the lattice basis) in Ed and L is the set of all vectors &Sgr;di=1 ai · bi, where the ai are integers. A lattice basis for L is said to be Minkowski reduced if each bi has minimal norm among all vectors b in L such that b1, ... ,bi-1, b can be extended to a basis for L.
A critical set of lattice parameters that are directly connected to SVP is &lgr;1(L), ... ,&lgr;d(L), where each &lgr;i(L) is the radius of the smallest ball centered at the origin containing i linearly independent lattice vectors.
This definition makes sense because of the discrete nature of lattices. The &lgr;(L) figure prominently in the complexity analysis of the authors’ greedy basis reduction algorithm.
The principal result of the paper is Theorem 4.2.1. There are some assumptions about precomputed inputs. The authors mention only that |b1| ≤ ... ≤ |bd| is assumed. Their greedy algorithm uses O( log |bd| · (1 + log |bd| - log &lgr;1(L)) ) bit operations and is shown to be correct for d ≤ 4. The O notation is independent of d, although the authors show that correctness is lost for d > 4. In a very careful but clear analysis, it is shown that the total cost of bit operations at each step of the algorithm is linear in log |bd|, yielding an overall quadratic bit complexity for the algorithm.
There are numerous interesting linear algebra lemmas in the paper and a clever application of low-dimensional Voronoï tessellations to the stepwise analysis. Some of this material may be of use to computational geometers. The detail of the paper is both its strength and its weakness. An exhaustive study of Minkowski reduction is carried out through dimension four, but the complications of the approach seem to become overwhelming as the dimension grows.
