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

Subhash Khot

doi:10.1016/j.jcss.2005.07.002

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

Subhash Khot

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	206-219
Number of pages	14
Journal	Journal of Computer and System Sciences
Volume	72
Issue number	2
DOIs	https://doi.org/10.1016/j.jcss.2005.07.002
State	Published - Mar 2006

Keywords

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

Access to Document

10.1016/j.jcss.2005.07.002

Cite this

@article{562b3012fc664c1aaa84e16e6d70a95b,

title = "Hardness of approximating the Shortest Vector Problem in high ℓp norms",

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-ε.",

keywords = "Approximation algorithms, Computational complexity, Hardness of approximation, Lattices, Shortest vector problem",

author = "Subhash Khot",

note = "Funding Information: A preliminary version of this paper appeared in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, 2003. This research was supported in part by Sanjeev Arora{\textquoteright}s NSF Awards 0205594, CCR 0098180 and the David and Lucile Packard Fellowship. E-mail address: [email protected].",

year = "2006",

month = mar,

doi = "10.1016/j.jcss.2005.07.002",

language = "English (US)",

volume = "72",

pages = "206--219",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

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

AU - Khot, Subhash

N1 - Funding Information: A preliminary version of this paper appeared in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, 2003. This research was supported in part by Sanjeev Arora’s NSF Awards 0205594, CCR 0098180 and the David and Lucile Packard Fellowship. E-mail address: [email protected].

PY - 2006/3

Y1 - 2006/3

N2 - 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-ε.

AB - 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-ε.

KW - Approximation algorithms

KW - Computational complexity

KW - Hardness of approximation

KW - Lattices

KW - Shortest vector problem

UR - http://www.scopus.com/inward/record.url?scp=32844474679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=32844474679&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2005.07.002

DO - 10.1016/j.jcss.2005.07.002

M3 - Article

AN - SCOPUS:32844474679

SN - 0022-0000

VL - 72

SP - 206

EP - 219

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -