Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry
Inapproximability of NP-complete Problems, Discrete Fourier Analysis, and Geometry
复制标题
NP 完全问题、离散傅立叶分析和几何的不可逼近性
DOI：
10.1142/9789814324359_0163
复制
发表时间：
2011
影响因子：
3
通讯作者：
Subhash Khot
中科院分区：
文献类型：
--
作者：
Subhash Khot
本文综述了计算机科学与数学中三个领域的最新结果：（1）计算NP完全问题近似解的困难性。(2)布尔超立方体上布尔函数的傅里叶分析。(3)几何学中的某些问题，特别是与等周和度量空间之间的嵌入有关的问题。
This article gives a survey of recent results that connect three areas in com- puter 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.