Project: Computation on Lattices

Philip Klein
Collaborator: David Gondek

Lattices
For vectors ${\bf b_1}, \ldots, {\bf b_n}$ in ${\bf Q}^d$, the set of integer linear combinations

$${\cal L} = \{ \lambda_1 {\bf b_1} + \cdots + \lambda_n {\bf b_n} \}$$

is called the lattice spanned by the vectors

Computational problems in lattices arise in

• computational algebra
• coding theory
• combinatorial optimization
• cryptology - security of several modern cryptosystems (including one commercially deployed) assumes difficulty of finding approximately optimal solutions to lattice problems.

Computational problems in lattices

• shortest vector problem:
  • input: vectors ${\bf b_1}, \ldots, {\bf b_n}$ representing a lattice
  • output: shortest nonzero vector in lattice generated

• closest vector problem:
  • input: vector ${\bf x}$, and vectors ${\bf b_1}, \ldots, {\bf b_n}$
  • output: vector in the lattice that is closest to ${\bf x}$
  (recent paper by Klein in Symposium on Discrete Algorithms: ``Finding the closest lattice vector when it's unusually close'')

Both problems are NP-hard. However, there is strong evidence that approximate solution is not NP-hard. Are there good approximation algorithms?