Hardness of approximating the shortest vector problem in high Lp norms

S. Khot

doi:10.1109/SFCS.2003.1238203

Hardness of approximating the shortest vector problem in high L_p norms

S. Khot

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 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	https://doi.org/10.1109/SFCS.2003.1238203
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

Access to Document

10.1109/SFCS.2003.1238203

Cite this

Khot, S. (2003). Hardness of approximating the shortest vector problem in high L_p norms. In Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 (pp. 290-297). Article 1238203 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2003-January). IEEE Computer Society. https://doi.org/10.1109/SFCS.2003.1238203

Hardness of approximating the shortest vector problem in high L_p norms. / Khot, S.
Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003. IEEE Computer Society, 2003. p. 290-297 1238203 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2003-January).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Khot, S 2003, Hardness of approximating the shortest vector problem in high L_p norms. in Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003., 1238203, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2003-January, IEEE Computer Society, pp. 290-297, 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, United States, 10/11/03. https://doi.org/10.1109/SFCS.2003.1238203

@inproceedings{9e57a9b4c18a41bd8f3a72c40e3c1850,

title = "Hardness of approximating the shortest vector problem in high Lp norms",

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

keywords = "Books, Computer science, Gaussian processes, Geometry, History, Lattices, Length measurement, Linear programming, Polynomials, Public key cryptography",

author = "S. Khot",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003 ; Conference date: 11-10-2003 Through 14-10-2003",

year = "2003",

doi = "10.1109/SFCS.2003.1238203",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "290--297",

booktitle = "Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003",

}

TY - GEN

T1 - Hardness of approximating the shortest vector problem in high Lp norms

AU - Khot, S.

PY - 2003

Y1 - 2003

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

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

KW - Books

KW - Computer science

KW - Gaussian processes

KW - Geometry

KW - History

KW - Lattices

KW - Length measurement

KW - Linear programming

KW - Polynomials

KW - Public key cryptography

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

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

U2 - 10.1109/SFCS.2003.1238203

DO - 10.1109/SFCS.2003.1238203

M3 - Conference contribution

AN - SCOPUS:40249102619

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

SP - 290

EP - 297

BT - Proceedings - 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003

PB - IEEE Computer Society

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

Y2 - 11 October 2003 through 14 October 2003

ER -