A Periodic Isoperimetric Problem Related to the Unique Games Conjecture
share
We prove the endpoint case of a conjecture of Khot and Moshkovitz related to the Unique Games Conjecture, less a small error. Let n≥2. Suppose a subset Ω of n-dimensional Euclidean space R^n satisfies -Ω=Ω^c and Ω+v=Ω^c for any standard basis vector v∈R^n. For any x=(x_1,...,x_n)∈R^n and for any q≥1, let x_q^q=|x_1|^q+...+|x_n|^q and let γ_n(x)=(2π)^-n/2e^-x_2^2/2 . For any x∈∂Ω, let N(x) denote the exterior normal vector at x such that N(x)_2=1. Let B={x∈R^nsin(π(x_1+...+x_n))≥0}. Our main result shows that B has the smallest Gaussian surface area among all such subsets Ω, less a small error: ∫_∂Ωγ_n(x)dx≥(1-6· 10^-9)∫_∂ Bγ_n(x)dx+∫_∂Ω(1-N(x)_1/√(n))γ_n(x)dx. In particular, ∫_∂Ωγ_n(x)dx≥(1-6· 10^-9)∫_∂ Bγ_n(x)dx. Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor 6· 10^-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.
READ FULL TEXT