A periodic isoperimetric problem related to the unique games conjecture

DOI10.1002/RSA.20877MaRDI QIDQ5113936zbMATH OpenOpenAlexWikidataFDO

Authors Steven Heilman

Publication date 19 June 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.00917

zbMATH Keywords

NP-hardnessisoperimetric problemunique games conjecture

Mathematics Subject Classification ID

Variational problems in a geometric measure-theoretic setting (49Q20) Geometric probability and stochastic geometry (60D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isoperimetric problems for polytopes (52B60)

Abstract: We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the Unique Games Conjecture, less a small error. Let $ngeq2$. Suppose a subset $Omega$ of $n$-dimensional Euclidean space $mathbb{R}^n$ satisfies $-Omega=Omeg{a}^c$ and $Omega+v=Omeg{a}^c$ (up to measure zero sets) for every standard basis vector $vinmathbb{R}^n$. For any $x=(x_1,ldots,x_n)inmathbb{R}^n$ and for any $qgeq1$, let $|x{|}_q^q=|x_1{|}^q+cdots+|x_n{|}^q$ and let $gamm{a}_n(x)=(2pi{)}^{-n/2}{e}^{-|x{|}_2^2/2}$ . For any $xinpartialOmega$, let $N(x)$ denote the exterior normal vector at $x$ such that $|N(x){|}_2=1$. Let $B=xinmathbb{R}^{n}colonsin(pi(x_1+cdots+x_n))geq0$. Our main result shows that $B$ has the smallest Gaussian surface area among all such subsets $Omega$, less a small error: ${\displaystyle }$ int_{partialOmega}gamma_{n}(x)dxgeq(1-6cdot 10^{-9})int_{partial B}gamma_{n}(x)dx+int_{partialOmega}Big(1-frac{|N(x)|_{1}}{sqrt{n}}Big)gamma_{n}(x)dx. ${\displaystyle }$ In particular, ${\displaystyle }$ int_{partialOmega}gamma_{n}(x)dxgeq(1-6cdot 10^{-9})int_{partial B}gamma_{n}(x)dx. ${\displaystyle }$ Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor $6cdot10^{-9}$ would 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.

Recommendations

• On Khot’s unique games conjecture
• Euclidean partitions optimizing noise stability
• scientific article; zbMATH DE number 7053310
• On the proof of the 2-to-2 games conjecture
• Unique games on the hypercube

This page was built for publication: A periodic isoperimetric problem related to the unique games conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113936)