Lattices that admit logarithmic worst-case to average-case connection factors
Chris Peikert, Alon Rosen · 2007
We exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n-dimensional lattices in the worst case, for γ(n) = O(√log n). The previously best known factor for any non-trivial class of lattices was γ(n) = Õ(n).