The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

Research output: Contribution to journalArticlepeer-review

249 Scopus citations

Abstract

We prove the following about the Nearest Lattice Vector Problem (in any lp norm), the Nearest Codeword 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 A/P-hard. 2. If for some ε > 0 there exists a polynomial-time algorithm that approximates the optimum within a factor of 2log0.5-ε n, then every NP language can be decided in quasi-polynomial deterministic time, i.e., NP ⊆ DTIME(npoly(log n)). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l norm. Also, for some of these problems we can prove the same result as above, but for a larger factor such as 2log1-ε n or nε. Improving the factor 2log0.5-ε n to √dimension for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l2 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)
Pages (from-to)317-331
Number of pages15
JournalJournal of Computer and System Sciences
Volume54
Issue number2
DOIs
StatePublished - Apr 1997

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations'. Together they form a unique fingerprint.

Cite this