2 log1-ε n hardness for the closest vector problem with preprocessing

We prove that for an arbitrarily small constant ε>0, assuming NP⊈ DTIME (2 log O 1-ε 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-ε n . This improves upon the previous hardness factor of (log n) δ for some δ>0 due to [AKKV05].

Authors

• Subhash Khot
• Preyas Popat
• Nisheeth K. Vishnoi

Keywords

• nearest codeword problem
• lattices
• hardness of approximation
• PCP
• closest vector problem