TY - GEN

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

AU - Arora, Sanjeev

AU - Babai, Laszlo

AU - Stern, Jacques

AU - Sweedyk, Z.

PY - 1993/12/1

Y1 - 1993/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0027795348&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027795348&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0027795348

SN - 0818643706

T3 - Annual Symposium on Foundatons of Computer Science (Proceedings)

SP - 724

EP - 733

BT - Annual Symposium on Foundatons of Computer Science (Proceedings)

A2 - Anon, null

PB - Publ by IEEE

T2 - Proceedings of the 34th Annual Symposium on Foundations of Computer Science

Y2 - 3 November 1993 through 5 November 1993

ER -