TY - JOUR
T1 - The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
AU - Arora, Sanjeev
AU - Babai, László
AU - Stern, Jacques
AU - Sweedyk, Z.
N1 - Funding Information:
* Research done while the author was at UC Berkeley, and was supported by an IBM Graduate Fellowship. -Partially supported by NSF grant CCR-9014562. Partially supported by NSF grant CCR-9201092 and Sandia National Laboratories.
PY - 1997/4
Y1 - 1997/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031119485&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0031119485&partnerID=8YFLogxK
U2 - 10.1006/jcss.1997.1472
DO - 10.1006/jcss.1997.1472
M3 - Article
AN - SCOPUS:0031119485
SN - 0022-0000
VL - 54
SP - 317
EP - 331
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
IS - 2
ER -