We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A periodic isoperimetric problem related to the unique games conjecture.
- Authors
Heilman, Steven
- Abstract
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 Rn satisfies −Ω = Ωc and Ω + v = Ωc (up to measure zero sets) for every standard basis vector v∈Rn. For any x=(x1,...,xn)∈Rn and for any q ≥ 1, let ‖x‖qq=|x1|q+...+|xn|q and let γn(x)=(2π)−n/2e−‖x‖22/2. For any x ∈ ∂Ω, let N(x) denote the exterior normal vector at x such that ‖N(x)‖2 = 1. Let B={x∈Rn:sin(π(x1+...+xn))≥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)‖1n)γ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.
- Subjects
ISOPERIMETRICAL problems; LOGICAL prediction; GAMES; SURFACE area
- Publication
Random Structures & Algorithms, 2020, Vol 56, Issue 1, p154
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20877