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

Research output: Contribution to journalArticle

Abstract

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
Volume72
Issue number2
DOIs
StatePublished - Mar 2006

Keywords

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

ASJC Scopus subject areas

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

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

  • Cite this