Summary: We prove the following about the nearest lattice vector problem (in any \(\ell_p\) 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 NP-hard. 2. If for some \(\varepsilon>0\) there exists a polynomial-time algorithm that approximates the optimum within afactor of \(2^{\log^{0.5-\varepsilon}n}\), then every NP language can be decided in quasi-polynomial deterministic time, i.e., \(\text{NP}\subseteq\text{DTIME}(n^{\text{poly}(\log n)})\).
Moreover, we show that result 2 also holds for the shortest lattice vector problem in the \(\ell_\infty\) norm. Also, for some of these problems we can prove the same result as above, but for a larger factor such as \(2^{\log^{1-\varepsilon}n}\) or \(n^\varepsilon\).
Improving the factor \(2^{\log^{0.5-\varepsilon}n}\) to \(\sqrt{\text{dimension}}\) for either of the lattice problems would imply the hardness of the shortest vector problem in \(\ell_2\) norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem.