Answers are grounded in this paper and cite their sources.
We prove the following about the Nearest Lattice Vector Problem (in any l/sub 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 /spl epsiv/>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2/sup log(0.5-/spl epsiv/)/ /sup n/ then NP is in quasi-polynomial deterministic time: NP/spl sube/DTIME(n/sup poly(log/ /sup n)/). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l/sub /spl infin// norm. Improving the factor 2/sup log(0.5-/spl epsiv/)/ /sup n/ to /spl radic/(dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l/sub 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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
No takes yet. Share an insight, caveat, or question.
Arora et al. (2002) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: