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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the International Congress of Mathematicians 2010, ICM 2010
Pages2676-2697
Number of pages22
StatePublished - Dec 1 2010
EventInternational Congress of Mathematicians 2010, ICM 2010 - Hyderabad, India
Duration: Aug 19 2010Aug 27 2010

Publication series

NameProceedings of the International Congress of Mathematicians 2010, ICM 2010

Other

OtherInternational Congress of Mathematicians 2010, ICM 2010
CountryIndia
CityHyderabad
Period8/19/108/27/10

Keywords

  • Approximation algorithms
  • Discrete Fourier analysis
  • Inapproximability
  • NP-completeness
  • Probabilistically checkable proofs

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Inapproximability of NP-complete problems, discrete fourier analysis, and geometry'. Together they form a unique fingerprint.

  • Cite this

    Khot, S. (2010). Inapproximability of NP-complete problems, discrete fourier analysis, and geometry. In Proceedings of the International Congress of Mathematicians 2010, ICM 2010 (pp. 2676-2697). (Proceedings of the International Congress of Mathematicians 2010, ICM 2010).