Hardness of approximating the Shortest Vector Problem in high ℓp norms

Research output: Contribution to journalArticlepeer-review


We present a new hardness of approximation result for the Shortest Vector Problem in ℓp norm (denoted by SVPp). Assuming NP ⊈ ZPP, we show that for every ε>0, there is a constant p(ε) such that for all integers p≥p(ε), the problem SVPp has no polynomial time approximation algorithm with approximation ratio p1-ε.

Original languageEnglish (US)
Pages (from-to)206-219
Number of pages14
JournalJournal of Computer and System Sciences
Issue number2
StatePublished - Mar 2006


  • Approximation algorithms
  • Computational complexity
  • Hardness of approximation
  • Lattices
  • Shortest vector problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Applied Mathematics
  • General Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics


Dive into the research topics of 'Hardness of approximating the Shortest Vector Problem in high ℓp norms'. Together they form a unique fingerprint.

Cite this