Complexity of Lattice Problems

Lattices are geometric objects that can be pictorially described as the set of intersection points of an infinite, regular n-dimensional grid. De­ spite their apparent simplicity, lattices hide a rich combinatorial struc­ ture, which has attracted the attention of great mathematicians over the last two centuries. Not surprisingly, lattices have found numerous ap­ plications in mathematics and computer science, ranging from number theory and Diophantine approximation, to combinatorial optimizatio