Search for: All records

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 spacesatisfies −Ω = Ω^cand Ω + v = Ω^c(up to measure zero sets) for every standard basis vector. For anyand for anyq ≥ 1, letand let. For anyx ∈ ∂Ω, letN(x) denote the exterior normal vector atxsuch that ‖N(x)‖₂ = 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⁻⁹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.