2 log1-ε n hardness for the closest vector problem with preprocessing
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi · 2012
We prove that for an arbitrarily small constant ε>0, assuming NP⊈ DTIME (2logO 1-ε n), the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than 2log1-ε n. This improves upon the previous hardness factor of (log n)δ for some δ>0 due to [AKKV05].