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

We prove the following about the Nearest Lattice Vector Problem (in any l_p 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 2^log(0.5-ε)n then NP is in quasi-polynomial deterministic time: NP contained in DTIME(n^{poly(log n)}). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l_∞ norm. Improving the factor 2^log0.5-εn to √dim for either of the lattice problems would imply the hardness of the Shortest Vector Problem in ℓ₂ 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.