Hardness of approximate optima in lattices, codes, and systems in linear equations

Sanjeev Arora, Laszlo Babai, Jacques Stern, Z. Sweedyk

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

80 Scopus citations

Abstract

We prove the following about the Nearest Lattice Vector Problem (in any lp norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some ε>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2log(0.5-ε)n then NP is in quasi-polynomial deterministic time: NP contained in DTIME(npoly(log n)). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l norm. Improving the factor 2log0.5-εn to √dim for either of the lattice problems would imply the hardness of the Shortest Vector Problem in ℓ2 norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems [FL], [BG+], either directly, or through a set-cover problem.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundatons of Computer Science (Proceedings)
Editors Anon
PublisherPubl by IEEE
Pages724-733
Number of pages10
ISBN (Print)0818643706
StatePublished - Dec 1 1993
Externally publishedYes
EventProceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
Duration: Nov 3 1993Nov 5 1993

Publication series

NameAnnual Symposium on Foundatons of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 34th Annual Symposium on Foundations of Computer Science
CityPalo Alto, CA, USA
Period11/3/9311/5/93

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Hardness of approximate optima in lattices, codes, and systems in linear equations'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1993). Hardness of approximate optima in lattices, codes, and systems in linear equations. In Anon (Ed.), Annual Symposium on Foundatons of Computer Science (Proceedings) (pp. 724-733). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.