Lattice problems in NP ∩ coNP

Dorit Aharonov, Oded Regev

Research output: Contribution to journalArticle

Abstract

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect CoNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series 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 [2003]. An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.

Original languageEnglish (US)
Pages (from-to)749-765
Number of pages17
JournalJournal of the ACM
Volume52
Issue number5
DOIs
StatePublished - Sep 2005

Keywords

  • Algorithms
  • Approximation
  • Fourier series
  • Lattices

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Lattice problems in NP ∩ coNP'. Together they form a unique fingerprint.

  • Cite this