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

Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$⊈$DTIME$(2^{{\log^{O(1/\eps)} n}})$, the preprocessing versions of the closest vector problem and…