Lattice problems in N P ∩ coNP

Dorit Aharonov, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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, Goldreich and Goldwasser, and Aharonov and Regev. 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. An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in. This route to proving purely classical results might be beneficial elsewhere.

Original languageEnglish (US)
Title of host publicationProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Pages362-371
Number of pages10
StatePublished - 2004
EventProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004 - Rome, Italy
Duration: Oct 17 2004Oct 19 2004

Other

OtherProceedings - 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004
CountryItaly
CityRome
Period10/17/0410/19/04

ASJC Scopus subject areas

  • Engineering(all)

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

  • Cite this

    Aharonov, D., & Regev, O. (2004). Lattice problems in N P ∩ coNP. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS (pp. 362-371)