### Abstract

We prove the following about the Nearest Lattice Vector Problem (in any l_{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 ε>0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2^{log(0.5-ε)n} then NP is in quasi-polynomial deterministic time: NP contained in DTIME(n^{poly(log n)}). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l_{∞} norm. Improving the factor 2^{log0.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.

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

Title of host publication | Annual Symposium on Foundatons of Computer Science (Proceedings) |

Editors | Anon |

Publisher | Publ by IEEE |

Pages | 724-733 |

Number of pages | 10 |

ISBN (Print) | 0818643706 |

State | Published - Dec 1 1993 |

Externally published | Yes |

Event | Proceedings of the 34th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA Duration: Nov 3 1993 → Nov 5 1993 |

### Publication series

Name | Annual Symposium on Foundatons of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

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

City | Palo Alto, CA, USA |

Period | 11/3/93 → 11/5/93 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Hardness of approximate optima in lattices, codes, and systems in linear equations'. Together they form a unique fingerprint.

## Cite this

*Annual Symposium on Foundatons of Computer Science (Proceedings)*(pp. 724-733). (Annual Symposium on Foundatons of Computer Science (Proceedings)). Publ by IEEE.