Hardness of approximating the shortest vector problem in high Lp norms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Lp norm within factor p1 - ∈ under randomized reductions. For large values of p, this improves the factor 21/p - δ hardness shown by D. Micciancio (1998).

Original languageEnglish (US)
Title of host publicationProceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
PublisherIEEE Computer Society
Pages290-297
Number of pages8
ISBN (Electronic)0769520405
DOIs
StatePublished - 2003
Event44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 - Cambridge, United States
Duration: Oct 11 2003Oct 14 2003

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2003-January
ISSN (Print)0272-5428

Other

Other44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003
CountryUnited States
CityCambridge
Period10/11/0310/14/03

Keywords

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

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hardness of approximating the shortest vector problem in high L<sub>p</sub> norms'. Together they form a unique fingerprint.

Cite this