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 journalArticle

200 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