Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell:
Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?
This paper proved the optimality of the Max-Cut algorithm by Goemans and Williamson, assuming the Unique Games Conjecture by Khot and another conjecture called “Majority is stablest”, which was later proved by Mossel, O’Donnell and Oleszkiewicz. Their work led the way of applying sophisticated Fourier techniques in this area.
Daniele Micciancio and Oded Regev:
Worst-Case to Average-Case Reductions Based on Gaussian Measures
This paper introduced the notion of “smoothing parameter” in the study of lattice problems, and substantially improved the worst-case to average-case connection factors in a number of problems such as the shortest vector problem, a research direction pioneered by Ajtai.