## Abstract

We show that for every ∈ > 0, there is a constant p(∈) such that for all integers p ≥ p(∈), it is NP-hard to approximate the shortest vector problem in L_{p} norm within factor p^{1 - ∈} under randomized reductions. For large values of p, this improves the factor 2^{1/p} - δ hardness shown by D. Micciancio (1998).

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

Title of host publication | Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 |

Publisher | IEEE Computer Society |

Pages | 290-297 |

Number of pages | 8 |

ISBN (Electronic) | 0769520405 |

DOIs | |

State | Published - 2003 |

Event | 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States Duration: Oct 11 2003 → Oct 14 2003 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2003-January |

ISSN (Print) | 0272-5428 |

### Other

Other | 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 |
---|---|

Country/Territory | United States |

City | Cambridge |

Period | 10/11/03 → 10/14/03 |

## Keywords

- Books
- Computer science
- Gaussian processes
- Geometry
- History
- Lattices
- Length measurement
- Linear programming
- Polynomials
- Public key cryptography

## ASJC Scopus subject areas

- General Computer Science

## Fingerprint

Dive into the research topics of 'Hardness of approximating the shortest vector problem in high L_{p}norms'. Together they form a unique fingerprint.