A periodic isoperimetric problem related to the unique games conjecture
A periodic isoperimetric problem related to the unique games conjecture
复制标题
与独特博弈猜想相关的周期性等周问题
DOI：
10.1002/rsa.20877
复制
发表时间：
2019
影响因子：
1
通讯作者：
Heilman, Steven
中科院分区：
文献类型：
--
作者：
Heilman, Steven
我们证明了Khot和Moshkovitz猜想的端点情况与唯一对策猜想有关，误差较小。Letn≥2。假设n维欧几里得空间的子集Ω满足- Ω = Ωcand Ω +v= Ωc（直到测量零集）对于每个标准基向量。对于任意和任意q≥1，令和令。对于任意x∈∂Ω，让N(x)表示外部法向量，使得‖N(x)‖2= 1。让。我们的主要结果表明，在所有这些子集中，b具有最小的高斯表面积Ω，误差较小：特别是，标准论证将这些结果扩展到噪声稳定性的相应弱不等式。除去因子6 × 10−9将证明Khot - Moshkovitz猜想的端点情况。最后，我们证明了Khot和Moshkovitz猜想的欧几里得类似。Khot和Moshkovitz的完整猜想为唯一博弈猜想的真实性提供了强有力的证据，唯一博弈猜想是理论计算机科学中的一个核心猜想，与P对NP问题密切相关。因此，我们的结果也为唯一对策猜想的真实性提供了证据。然而，本文并没有证明唯一对策猜想的任何情况。
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the unique games conjecture, less a small error. Letn≥ 2. Suppose a subset Ω ofn‐dimensional Euclidean space satisfies −Ω = Ωcand Ω +v= Ωc(up to measure zero sets) for every standard basis vector . For any and for anyq≥ 1, let and let . For anyx∈∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖2= 1. Let . Our main result shows thatBhas the smallest Gaussian surface area among all such subsets Ω, less a small error: In particular, Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6 × 10−9would prove the endpoint case of the Khot‐Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.
登录
查看更多内容
扩展问题之间的约简
DOI：
10.1109/ccc.2012.43
发表时间：
2010
期刊：
2012 IEEE 27th Conference on Computational Complexity
影响因子：
--
作者：
P. Raghavendra;David Steurer;Madhur Tulsiani
通讯作者：
Madhur Tulsiani
周期性相分离：周期性 Cahn-Hilliard 和等周问题
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Rustum Choksi;P. Sternberg
通讯作者：
P. Sternberg
论独特游戏猜想（特邀调查）
DOI：
--
发表时间：
2005
期刊：
2010 IEEE 25th Annual Conference on Computational Complexity
影响因子：
--
作者：
Subhash Khot
通讯作者：
Subhash Khot
Ornstein-Uhlenbeck 速度过程的几何界限
影响因子：
2
作者：
C. Borell
通讯作者：
C. Borell
影响因子：
2.4
作者：
Theil, F
通讯作者：
Theil, F