TY - GEN
T1 - Hardness of approximation
AU - Khot, Subhash
N1 - Funding Information:
Acknowledgements. This work is supported by NSF grants CCF-0832795, 1061938, 1422159, and Simons Collaboration on Algorithms and Geometry grant.
PY - 2014
Y1 - 2014
N2 - This article accompanies the talk given by the author at the International Congress of Mathematicians, 2014. The article sketches some connections between approximability of NP-complete problems, analysis and geometry, and the role played by the Unique Games Conjecture in facilitating these connections. For a more extensive introduction to the topic, the reader is referred to survey articles [39, 40, 64].
AB - This article accompanies the talk given by the author at the International Congress of Mathematicians, 2014. The article sketches some connections between approximability of NP-complete problems, analysis and geometry, and the role played by the Unique Games Conjecture in facilitating these connections. For a more extensive introduction to the topic, the reader is referred to survey articles [39, 40, 64].
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=85086377454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086377454&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85086377454
T3 - Proceeding of the International Congress of Mathematicans, ICM 2014
SP - 711
EP - 728
BT - Plenary Lectures and Ceremonies
A2 - Jang, Sun Young
A2 - Kim, Young Rock
A2 - Lee, Dae-Woong
A2 - Yie, Ikkwon
PB - KYUNG MOON SA Co. Ltd.
T2 - 2014 International Congress of Mathematicans, ICM 2014
Y2 - 13 August 2014 through 21 August 2014
ER -