Approximating SVP_infty to within Almost-Polynomial Factors is NP-hard

摘要

This paper shows SVP_infty and CVP_infty to be NP-hard to approximate to within any factor up to $n^{1/loglog n}$. This improves on the best previous result cite{ABSS} that showed quasi-NP-hardness for smaller factors, namely $2^{log^{1-epsilon}n}$ for any constant $epsilon>0$. We show a direct reduction from SAT to these problems, that combines ideas from cite{ABSS} and from cite{DKS,DKRS}, along with some modifications. Our result is obtained without relying on the PCP characterization of NP, although some of our techniques are derived from the proof of the PCP characterization itself cite{DFKRS}.