Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry
Subhash Khot · Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) · 2011
Abstract. This article gives a survey of recent results that connect three areas in computer science and mathematics: (1) (Hardness of) computing approximate solutions to NP-complete problems. (2) Fourier analysis of boolean functions on boolean hypercube. (3) Certain problems in geometry, especially related to isoperimetry and embeddings between metric spaces.