45th Annual IEEE Symposium on Foundations of Computer Science
Download PDF

Abstract

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of \sqrt n lie in Np intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [7], Goldreich and Goldwasser [13], and Aharonov and Regev [2]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier transform over the lattice. This technique might be useful elsewhere - we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev [25]. An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in [2]. This route to proving purely classical results might be beneficial elsewhere.
Like what you’re reading?
Already a member?Sign In
Member Price
$11
Non-Member Price
$21
Add to CartSign In
Get this article FREE with a new membership!

Related Articles