The hardness of approximate optima in lattices, codes, and systems of linear equations

We prove the following about the Nearest Lattice Vector Problem (in any I-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 epsilon>0 there exists a polynomial-time algorithm that approximates the optimum within a factor of 2(log0.5-epsilon n), then every NP language can be decided in quasi-polynomial deterministic time, i.e., NP subset of or equal to DTIME(n(poly(log n))). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the I-infinity norm. Also, for some of these problems we can prove the same result as above, but for a larger factor such as 2(log1-epsilon n) or n(epsilon). Improving the factor 2(log0.5-epsilon n) to root dimension for either of the lattice problems would imply the hardness of the Shortest Vector Problem in I-2 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. (C) 1997 Academic Press.