We survey some recent developments in the study of the complexity of lattice problems. After a discussion of some problems on lattices which can be algorithmically solved efficiently, our main focus is the recent progress on complexity results of intractability. We will discuss Ajtai's worst-case/ average-case connections, NP-hardness and non-NP-hardness, ... more >>>

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate to within any factor up to $n^{1/\log\log 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 ... more >>>