TY - GEN

T1 - Inapproximability of NP-complete problems, discrete fourier analysis, and geometry

AU - Khot, Subhash

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Discrete Fourier analysis

KW - Inapproximability

KW - NP-completeness

KW - Probabilistically checkable proofs

UR - http://www.scopus.com/inward/record.url?scp=84877918367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877918367&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84877918367

SN - 9814324302

SN - 9789814324304

T3 - Proceedings of the International Congress of Mathematicians 2010, ICM 2010

SP - 2676

EP - 2697

BT - Proceedings of the International Congress of Mathematicians 2010, ICM 2010

T2 - International Congress of Mathematicians 2010, ICM 2010

Y2 - 19 August 2010 through 27 August 2010

ER -