## Abstract

We prove the following about the Nearest Lattice Vector Problem (in any l_{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 A/P-hard. 2. If for some ε > 0 there exists a polynomial-time algorithm that approximates the optimum within a factor of 2^{log0.5-ε n}, then every NP language can be decided in quasi-polynomial deterministic time, i.e., NP ⊆ DTIME(n^{poly(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 2^{log1-ε n} or n^{ε}. Improving the factor 2^{log0.5-ε n} to √dimension for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l_{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.

Original language | English (US) |
---|---|

Pages (from-to) | 317-331 |

Number of pages | 15 |

Journal | Journal of Computer and System Sciences |

Volume | 54 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1997 |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics