Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing

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). © 2014 Society for Industrial and Applied Mathematics.


Published in:
SIAM Journal on Computing, 43, 3, 1184-1205
Year:
2014
Publisher:
Society for Industrial and Applied Mathematics
ISSN:
1095-7111
Laboratories:




 Record created 2015-09-16, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)