Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing
Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi · SIAM Journal on Computing · 2014
We prove that for an arbitrarily small constant $\varepsilon>0,$ the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor $2^{\log ^{1-\varepsilon}n}$, under the assumption that NP $ ot \subseteq$ SIZE$(2^{\log^{O(1/\varepsilon)} n})$.