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 -