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

AbstractWe prove the following about the Nearest Lattice Vector Problem (in anylpnorm), 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 isNP-hard. 2. If for someε>0 there exists a polynomial-time algorithm that approximates the optimum within a factor of 2log0.5−εn, then everyNPlanguage can be decided in quasi-polynomial deterministic time, i.e.,NP⊆DTIME(npoly(logn)). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in thel∞norm. Also, for some of these problems we can prove the same result as above, but for a larger factor such as 2log1−εnornε. Improving the factor 2log0.5−εntodimensionfor either of the lattice problems would imply the hardness of the Shortest Vector Problem inl2norm; 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