My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, Generating hard instances of lattice problems, which indicates a connection between worst-case hard and average-case hard lattice problems. This proof is difficult for me to understand. Is there a clear exposition of this proof in the literature?
$\begingroup$
$\endgroup$
-
5$\begingroup$ You can try reading more recent papers such as cims.nyu.edu/~regev/papers/average.pdf, or Oded Regev's lecture notes cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/… (you might want to read the entire course). $\endgroup$ – Yuval Filmus Nov 5 '14 at 14:53
$\begingroup$
$\endgroup$
You can try reading more recent papers such as Worst-case to Average-case Reductions based on Gaussian Measures by Miccancio and Regev, or Regev's lecture notes on the subject (you might want to read through the entire course).
answered Nov 6 '14 at 4:42
