ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-119 | 4th September 2011 22:42

$2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

RSS-Feed




TR11-119
Authors: Subhash Khot, Preyas Popat, Nisheeth Vishnoi
Publication: 11th September 2011 16:49
Downloads: 713
Keywords: 


Abstract:

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta > 0$ due to \cite{Alekhnovich Khot Kindler Vishnoi 05}.



ISSN 1433-8092 | Imprint