id: 05971212
dt: a
an: 05971212
au: Khot, Subhash
ti: Inapproximability of NP-complete problems, discrete Fourier analysis, and
    geometry.
so: Bhatia, Rajendra (ed.) et al., Proceedings of the international congress of
    mathematicians (ICM 2010), Hyderabad, India, August 19‒27, 2010. Vol.
    IV: Invited lectures. Hackensack, NJ: World Scientific; New Delhi:
    Hindustan Book Agency (ISBN 978-981-4324-34-2/hbk;
    978-81-85931-08-3/hbk; 978-981-4324-31-1/set; 978-981-4324-35-9/ebook).
    2676-2697 (2011).
py: 2011
pu: Hackensack, NJ: World Scientific; New Delhi: Hindustan Book Agency
la: EN
cc: 
ut: NP-completeness; approximation algorithms; inapproximability;
    probabilistically checkable proofs; discrete Fourier analysis
ci: 
li: http://ebooks.worldscinet.com/ISBN/9789814324359/9789814324359_0163.html
ab: Summary: 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.
rv: