The systematic normal form of lattices, and their algorithmic applications. [joint work with Peter Shor; Lior Eldar]

  • Lior Eldar | MIT

The systematic normal form of lattices is a new echelon form of lattices in which the entries obey a certain co-primality condition. These lattices can be used to approximate efficiently any lattice, and hence are as hard to solve as any lattice. We show that this special structure gives rise to several interesting mathematical properties, connecting their primal and dual lattices, which in turn offer certain natural quantum and classical computational primitives which are otherwise not known to exist. We present these primitives as a possible handle to make progress to solve computationally-hard lattice problems.

Watch Next