An Improved Worst-case to Average-Case Connection for Lattice Problems (extended abstract)
Jin‐Yi Cai · 1997
We improve a connection of the worst-case complexity and the average-case complexity of some well-known lattice problems. This fascinating connection was first discovered by Ajtai [1] in 1996. We improve the exponent of this connection from 8 to 3:5 + ffl. Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Research supported in part by NSF grants CCR-9319393 and CCR-9634665, and an Alfred P. Sloan Fellowship. Email: [email protected] y Department of Computer Science, State University of New York at Buffalo, Buffalo, NY 14260. Research supported in part by NSF grants CCR-9319393 and CCR-9634665. Email: [email protected] 1 Introduction A lattice L is a discrete additive subgroup of R n . There are many fascinating problems concerning lattices, both from a structural and from an algorithmic point of view [12, 20, 11, 13]. The study of lattice problems can be traced back to Gauss, Dirichlet and Hermite, among others [8, 6, 14]. The subje...