Almost polynomial factor hardness for closest vector problem with preprocessing

Subhash A. Khot; Preyas Popat; Nisheeth K. Vishnoi

doi:10.1137/130919623

Almost polynomial factor hardness for closest vector problem with preprocessing

Subhash A. Khot, Preyas Popat, Nisheeth K. Vishnoi

Computer Science

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

Abstract

We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2^log1-en, under the assumption that NP ⊈ SIZE(2^logO(1/e)n).

Original language	English (US)
Pages (from-to)	1184-1205
Number of pages	22
Journal	SIAM Journal on Computing
Volume	43
Issue number	3
DOIs	https://doi.org/10.1137/130919623
State	Published - 2014

Keywords

Closest vector problem
Hardness of approximation
Smooth label cover
Sum check protocol

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1137/130919623

Cite this

@article{cfaf9332ca734eb7b29bc95fc95b73a8,

title = "Almost polynomial factor hardness for closest vector problem with preprocessing",

abstract = "We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n).",

keywords = "Closest vector problem, Hardness of approximation, Smooth label cover, Sum check protocol",

author = "Khot, {Subhash A.} and Preyas Popat and Vishnoi, {Nisheeth K.}",

year = "2014",

doi = "10.1137/130919623",

language = "English (US)",

volume = "43",

pages = "1184--1205",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Almost polynomial factor hardness for closest vector problem with preprocessing

AU - Khot, Subhash A.

AU - Popat, Preyas

AU - Vishnoi, Nisheeth K.

PY - 2014

Y1 - 2014

N2 - We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n).

AB - We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n).

KW - Closest vector problem

KW - Hardness of approximation

KW - Smooth label cover

KW - Sum check protocol

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

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

U2 - 10.1137/130919623

DO - 10.1137/130919623

M3 - Article

AN - SCOPUS:84904796466

SN - 0097-5397

VL - 43

SP - 1184

EP - 1205

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Almost polynomial factor hardness for closest vector problem with preprocessing

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this