A PERIODIC ISOPERIMETRIC PROBLEM RELATED TO THE UNIQUE GAMES CONJECTURE

STEVEN HEILMAN

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 ℝ^{n} satisfies −Ω = Ω^{c} and Ω + v = Ω^{c} (up to measure zero sets) for every standard basis vector v ∈ ℝ^{n}. For any x = (x_{1}, …, x_{n}) ∈ ℝ^{n} and for any q ≥ 1, let ∥x∥_{q}^{q} = |x_{1}|^{q} + ⋯ + |x_{n}|^{q} and let γ_{n}(x) = (2π)^{−n/2}e^{−∥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 ∈ ℝ^{n}: sin(π(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 − \frac{∥N(x)∥_{1}}{\sqrt{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.

1. Introduction

The Unique Games Conjecture is a central unresolved problem in theoretical computer science, of similar significance to the P versus NP problem. That is, proving or disproving the Unique Games Conjecture will have significant ramifications throughout both computer science and mathematics [Kho10]. Both positive and negative evidence has been found for the Unique Games Conjecture since its formulation in 2002 by Khot [Kho02], but the Conjecture remains open. Khot’s Conjecture can be formulated as follows.

Definition 1.1 (Gap Unique Games Problem [Kho02, KKMO07]). Let 0 < s < c < 1 and let p > 1 be a prime. We refer to GapUG_{p}(c, s) as the following problem. Suppose a_{2}, a_{4}, …, a_{2n} ∈ ℤ/pℤ are fixed, x_{1}, …, x_{k} are variables with k ≤ n, 1 ≤ i_{1}, …, i_{2n} ≤ k, and we have a system of n two-term linear equations in ℤ/pℤ of the form x_{i_{1}} − x_{i_{2}} = a_{2}, x_{i_{3}} − x_{i_{4}} = a_{4}, …, x_{i_{2n−1}} − x_{i_{2n}} = a_{2n}. Let OPT be the maximum number of these linear

Date: July 9, 2021. Supported by NSF Grant DMS 1708908.

equations that can be satisfied by any assignment of values to the variables x_{i_{1}}, …, x_{i_{2n}}. Decide whether OPT ≥ cn or OPT ≤ sn.

As |c − s| increases to a value near 1, the GapUG problem becomes easier to solve. The Unique Games Conjecture says that, even when |c − s| is very close to 1, the GapUG problem is still hard to solve. That is, the GapUG problem is nearly as hard as one could expect.

Conjecture 1.2 (Unique Games Conjecture [Kho02, KKMO07]). For any ε > 0, there exists some prime p = p(ε) such that GapUG_{p}(1 − ε, ε) is NP-hard.

In short, Conjecture 1.2 says that approximately solving linear equations is hard. If all n of the equations could be satisfied, then classical Gaussian elimination could find values for the variables x_{i_{1}}, …, x_{i_{2n}} satisfying all of the linear equations in polynomial time in n. On the other hand, if only almost all of the equations can be satisfied, then it is hard to satisfy a small fraction of them, according to Conjecture 1.2. Note also that p must depend on ε in Conjecture 1.2, since if p is fixed, then a random assignment of values to the variables will satisfy a positive fraction of the linear equations.

The most significant negative evidence for Conjecture 1.2 is a subexponential time algorithm for the Unique Games Problem [ABS10]. That is, there exists a constant 0 < a < 1 such that, for any ε > 0, and for any prime p > 1, there is an algorithm with runtime exp(pn^{ε^{a}}) such that, if (1 − ε)n equations among n two-term linear equations in ℤ/pℤ of the form x_{1}−x_{2} = a_{2}, x_{3}−x_{4} = a_{4}, …, x_{2n−1}−x_{2n} = a_{2n} can be satisfied, then the algorithm can satisfy 1 − ε^{a} of the equations. If the quantity exp(pn^{ε^{a}}) could be replaced by a polynomial in n, then Conjecture 1.2 would be false.

A recent breakthrough of [KMS18], culminating the work of [DKK^{+}18, KMS17, KMMS18] and [BKS19], gives significant positive evidence for Conjecture 1.2.

Theorem 1.3 ([KMS18, page 55]). For any ε > 0, there exists some prime p = p(ε) such that GapUG_{p}(\frac{1}{2} − ε, ε) is NP-hard.

As discussed in [KMS18], since the subexponential algorithm of [ABS10] solves the GapUG problem for certain parameters 0 < s < c < 1 where c can have values in (0, 1), this “... is a compelling evidence, in our opinion, that the known algorithmic attacks are (far) short of disproving the Unique Games Conjecture.”

Due to Theorem 1.3, it remains to investigate the hardness of GapUG_{p}(c, s) where c ≥ 1/2. In a 2015 paper, Khot and Moshkovitz [KM16] show that if a certain Gaussian noise stability inequality holds, then a weaker version of the NP-hardness of GapUG_{2}(1 − ε, 1 − Ω(\sqrt{ε})) is true for any 0 < ε < 1. We describe this noise stability inequality below in Conjecture 1.8. The weaker version of the GapUG problem is stated in [KM16, page 3]. Resolving this weaker conjecture would provide significant evidence for the hardness of GapUG_{p}(1 − ε, 1 − Ω(\sqrt{ε})) and for Conjecture 1.2 itself. (Recall that f: [0, 1] → ℝ satisfies f = Ω(\sqrt{ε}) if lim sup_{ε→0^{+}} |f(ε)/\sqrt{ε}| > 0. We change notation below so that Ω denotes a subset of Euclidean space.)

For a review of positive and negative evidence for the Unique Games Conjecture, see [AKKT15] and also [ABS10, RST12, BBH^{+}12]. See also [HNW19, Corollary 5.3] for more recent positive evidence.

For more background on the Unique Games Conjecture and its significance, see [Kho10].

Definition 1.4 (Gaussian density). Let n be a positive integer. Define the Gaussian density so that, for any x = (x_{1}, …, x_{n}) ∈ ℝ^{n},

γ_{n}(x) := (2π)^{−n/2}e^{−(x_{1}^{2}+···+x_{n}^{2})/2}.

Recall that a standard n-dimensional Gaussian random vector X satisfies

ℙ(X ∈ C) = ∫_{C} dγ_{n}(x), ∀ C ⊆ ℝ^{n}.

Let f: ℝ^{n} → [0, 1] and let ρ ∈ (−1, 1), define the Ornstein-Uhlenbeck operator with correlation ρ applied to f by

\begin{aligned}T_{ρ}f(x) & := ∫_{ℝ^{n}} f(xρ + y\sqrt{1 − ρ^{2}})dγ_{n}(y) \\ & = (1 − ρ^{2})^{−n/2}(2π)^{−n/2} ∫_{ℝ^{n}} f(y)e^{− \frac{∥y−ρx∥^{2}_{2}}{2(1−ρ^{2})}} dy,  ∀ x ∈ ℝ^{n}. \end{aligned}  (1)

T_{ρ} is a parametrization of the Ornstein-Uhlenbeck operator. T_{ρ} is not a semigroup, but it satisfies T_{ρ_{1}}T_{ρ_{2}} = T_{ρ_{1}ρ_{2}} for all ρ_{1}, ρ_{2} ∈ (0, 1). We have chosen this definition since the usual Ornstein-Uhlenbeck operator is only defined for ρ ∈ [0, 1].

Definition 1.5 (Noise Stability). Let Ω ⊆ ℝ^{n}. Let ρ ∈ (−1, 1). We define the noise stability of the set Ω with correlation ρ to be

∫_{ℝ^{n}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)dγ_{n}(x) =^{(1)} (2π)^{−n}(1 − ρ^{2})^{−n/2} ∫_{Ω} ∫_{Ω} e^{\frac{−∥x∥^{2}_{2}−∥y∥^{2}_{2}+2ρ⟨x,y⟩}{2(1−ρ^{2})}} dxdy.

Equivalently, if X, Y ∈ ℝ^{n} are independent n-dimensional standard Gaussian distributed random vectors, then

∫_{ℝ^{n}} 1_{Ω}(x)T_{ρ}1_{Ω}(x)dγ_{n}(x) = ℙ (X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) .

1.1. Khot-Moshkovitz Conjecture on the Noise Stability of Periodic Sets. Recall that the standard basis vectors v_{1}, …, v_{n} ∈ ℝ^{n} are defined so that, for any 1 ≤ i ≤ n, v_{i} has a 1 entry in its i^{th} coordinate, and zeros in the other coordinates.

Definition 1.6 (Periodic Set). We say a subset Ω ⊆ ℝ^{n} is periodic if Ω + v = Ω^{c} for every standard basis vector v ∈ ℝ^{n}, and −Ω = Ω^{c} (up to changes to Ω of Lebesgue measure zero).

Definition 1.7 (Periodic Half Space). Let ε_{1}, …, ε_{n} ∈ {−1, 1}. We define a periodic half space to be any set B ⊆ ℝ^{n} of the form

B = {x = (x_{1}, …, x_{n}) ∈ ℝ^{n}: sin(π(ε_{1}x_{1} + ⋯ + ε_{n}x_{n})) ≥ 0}.

The following Conjecture of Khot and Moshkovitz [KM16] says that periodic half spaces are the most noise stable periodic sets.

Conjecture 1.8 ([KM16]). Let 1/2 < ρ < 1. Let Ω ⊆ ℝ^{n} be a periodic set. Let B ⊆ ℝ^{n} be a periodic half space. Let X, Y ∈ ℝ^{n} be independent standard Gaussian random vectors. Then

ℙ (X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) ≤ ℙ (X ∈ B, ρX + Y \sqrt{1 − ρ^{2}} ∈ B) .

B

Figure 1. A periodic half space B.

Conjecture 1.8 implies that a weaker version of Conjecture 1.2 holds; see [KM16, page 3] and [KM16, page 5]. For this reason, this paper studies Conjecture 1.8. In fact, as stated on [KM16, page 5], a stronger version of Conjecture 1.8 is required for the main application of [KM16], but we only focus on Conjecture 1.8 in this work. We are unable to prove Conjecture 1.8, so we instead study the endpoint case ρ → 1^{−} of Conjecture 1.8. As discussed in [KM16], Conjecture 1.8 is most interesting and relevant to Conjecture 1.2 when ρ approaches 1. That is, the case of Conjecture 1.8 most relevant to the Unique Games Conjecture occurs when ρ → 1^{−}.

It is well known that, as ρ → 1^{−}, the noise stability (when normalized appropriately) converges to Gaussian surface area. That is, if ∂Ω is a C^{∞} manifold, then [Kan11, Lemma 3.1] [Led96, Proposition 8.5] [DMN17]

lim_{ρ→1^{−}} \frac{\sqrt{2π}}{cos^{−1}(ρ)} [ℙ(X ∈ Ω) − ℙ (X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω)] = ∫_{∂Ω} γ_{n}(x)dx. (2)

Here and below, dx denotes Lebesgue measure restricted to the surface ∂Ω ⊆ ℝ^{n}. Recall that a C^{∞} manifold is locally the graph of a C^{∞} function.

Letting ρ → 1^{−} in Conjecture 1.8 and applying (2) (along with ℙ(X ∈ Ω) = ℙ(X ∈ B) = 1/2 which follows since −Ω = Ω^{c}), we obtain the following statement.

Conjecture 1.9 (Endpoint ρ → 1^{−} case of Conjecture 1.8). Let Ω ⊆ ℝ^{n} be a periodic set. Let B ⊆ ℝ^{n} be a periodic half space. Then

∫_{∂Ω} γ_{n}(x)dx ≥ ∫_{∂B} γ_{n}(x)dx.

1.2. Our Contribution. Our main result verifies Conjecture 1.9, up to a small error, nearly verifying the endpoint ρ = 1 case of Conjecture 1.8, and providing evidence for the p = 2 case of Conjecture 1.2. Theorem 1.10 also demonstrates that, if a set Ω is far from a periodic half space, in the sense that the normal vector typically has ℓ_{1} norm less than \sqrt{n}, then Ω has large Gaussian surface area. Such a “robustness” statement was required in the application of [KM16] to the Unique Games Conjecture, Conjecture 1.2.

Theorem 1.10 (Main Theorem; Weak Version of Conjecture 1.9). Let n ≥ 2. Let Ω ⊆ ℝ^{n} be a periodic set. Let B ⊆ ℝ^{n} be a periodic half space. Assume ∂Ω is a C^{∞} manifold. Then

∫_{∂Ω} γ_{n}(x)dx ≥ (1 − 6 · 10^{−9}) ∫_{∂B} γ_{n}(x)dx + ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx.  (3)

In particular,

∫_{∂Ω} γ_{n}(x)dx ≥ (1 − 6 · 10^{−9}) ∫_{∂B} γ_{n}(x)dx.  (4)

The right-most term of (3) is nonnegative by the Cauchy-Schwarz inequality.

Standard methods can derive from Theorem 1.10 the following statement for noise stability.

Corollary 1.11 (Weak Version of Khot-Moshkovitz Conjecture 1.8). Let d > 0. Let n ≥ 2. Let g: ℝ^{n} → ℝ be a degree d polynomial. Let Ω = {x ∈ ℝ^{n}: g(x) ≥ 0}. Let X, Y be independent standard n-dimensional Gaussian random vectors. Let 1/2 < ρ < 1. Assume that Ω is a periodic set and ∂Ω is a C^{∞} manifold. Let B ⊆ ℝ^{n} be a periodic half space. Then

ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) ≤ ℙ(X ∈ B, ρX + Y \sqrt{1 − ρ^{2}} ∈ B) + 3 · 10^{−9}

− \begin{matrix}√ & \overline{1 − ρ^{2}} \\ √ & \overline{2π} \end{matrix} ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx + o(\sqrt{1 − ρ^{2}}).

In particular,

ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) ≤ ℙ(X ∈ B, ρX + Y \sqrt{1 − ρ^{2}} ∈ B) + 3 · 10^{−9} + o(\sqrt{1 − ρ^{2}}).

Here the implied constants o(\sqrt{1 − ρ^{2}}) can depend on Ω.

Remark 1.12. If ρ is close to 1 and ∫_{∂Ω} γ_{n}(x)dx is small, then Corollary 1.11 is vacuous. In particular, if \sqrt{1 − ρ^{2}} < 3 · 10^{−9}n^{−1/2}, then the 3 · 10^{−9} term will be larger than the ensuing term.

Remark 1.13. The “robustness” terms ∫_{∂Ω} (1− \begin{matrix}∥N(x)∥ & _{1} \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx in Theorem 1.10 and Corollary 1.11 can be improved slightly. See Remark 3.3 below.

Remark 1.14. Under certain assumptions, the “robustness” term ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & _{1} \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx is comparable to the Gaussian measure of the symmetric difference of Ω and a periodic half space B. See Remark 3.5 below for a slightly more precise statement.

If we modify the random variable X in Conjecture 1.8, then we can improve Corollary 1.11.

Corollary 1.15 (Modified Version of Khot-Moshkovitz Conjecture 1.8). Let n ≥ 2. Let Ω ⊆ ℝ^{n} be a periodic set such that ∂Ω is a C^{∞} manifold. Let X, Y ∈ ℝ^{n} be independent random variables such that X is uniformly distributed in [−1/2, 1/2]^{n} and Y is a standard Gaussian random vector. Let 0 < ε < 1/2. Let B ⊆ ℝ^{n} be a periodic half space. Then

ℙ(X ∈ Ω, X + εY ∈ Ω) ≤ ℙ(X ∈ B, X + εY ∈ B) − ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )dx + o(ε).

In particular,

ℙ(X ∈ Ω, X + εY ∈ Ω) ≤ ℙ(X ∈ B, X + εY ∈ B) + o(ε).

Here the implied constants o(ε) can depend on Ω.

1.3. Background on Gaussian Isoperimetry. In the 1970s, Borell and Sudakov-Tsirelson proved the Gaussian Isoperimetric Inequality [Bor75, SC74]: among all sets Ω ⊆ ℝ^{n} of fixed Gaussian measure ∫_{Ω} dγ_{n}(x), the smallest Gaussian surface area ∫_{∂Ω} γ_{n}(x)dx occurs when Ω is a half space. That is, Ω is the set of points lying on one side of a hyperplane. The works [Bor75, SC74] used symmetrization methods. That is, they replace any set Ω with a “more symmetric” set with the same Gaussian measure and with smaller Gaussian surface area. In 1985, Borell generalized the Gaussian Isoperimetric Inequality to noise stability [Bor85]: for any 0 < ρ < 1, among among all sets Ω ⊆ ℝ^{n} of fixed Gaussian measure, the maximum value of ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) occurs when Ω is a half space. Once again, Borell used symmetrization methods. Borell’s result [Bor85] was further elucidated by many authors, including [Led96, BS01].

The inequality of [Bor85] gained renewed attention due to its applications in theoretical computer science. In particular, the inequality of [Bor85] was a key component in the proof of the Majority is Stablest Theorem [MOO10], and in the proof of the sharp Unique Games hardness of the MAX-CUT problem [KKMO07, MOO10]. Due to this renewed interest, Borell’s result was re-proved and strengthened in [MN15, Eld15]. The results of [MN15, Eld15] show that if a set Ω ⊆ ℝ^{n} is close to maximizing the noise stability ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω), then Ω is close to a half space. The work [MN15] uses heat flow methods, and [Eld15] uses stochastic calculus methods. All known proofs of Borell’s inequality [Bor85] somehow use translation invariance of the inequality: any translation of a half space is still a half space.

Note that Conjectures 1.8 and 1.9 do not have any translation invariance property. It is possible to translate a periodic half space and produce a set that is a not a periodic half space. For this reason, all known proofs of Gaussian isoperimetric inequalities seem entirely unable to prove Conjectures 1.8 or 1.9.

1.4. Method of Proof of the Main Result. Theorem 1.10 is proven in an almost elementary way. Conjectures 1.8 and 1.9 can be restated as isoperimetric problems on the torus equipped with the heat kernel measure on the torus. For example, the Poisson Summation formula allows the following equivalent formulation of Conjecture 1.9.

Conjecture 1.16 (Restatement of Conjecture 1.9). The minimum value of

∫_{[0,1]^{n}∩(∂Ω)} ∑_{z∈ℤ^{n}} e^{2πi⟨y,z⟩}e^{−2π^{2}∥z∥_{2}^{2}}dy.

over all periodic sets Ω ⊆ ℝ^{n} occurs when Ω is a periodic half space.

Here ⟨y, z⟩ := ∑_{i=1}^{n} y_{i}z_{i} for any y, z ∈ ℝ^{n}, and ∥z∥_{2}^{2} = ⟨z, z⟩.

The heat kernel measure p_{n}(y) := ∑_{z∈ℤ^{n}} e^{2πi⟨y,z⟩}e^{−2π^{2}∥z∥_{2}^{2}} is very close to the constant function 1 (see Lemma 3.2). This fact may make it difficult to apply Gaussian isoperimetric methods to approach Conjecture 1.9. So, we instead treat Conjecture 1.9 as an essentially Euclidean problem. That is, we solve exactly the analogue of Conjecture 1.16 when the integrand is the constant function 1. In this case, an exact solution follows by projecting ∂B onto each facet of the unit cube, and noting that this projection is injective. The error between this exact solution and the integral in Conjecture 1.16 is then small since p_{n} is a product measure (see Lemma 3.1). This approach allows us to prove Theorem 1.10 using an elementary argument. The error term 6 · 10^{−9} arises since this is roughly the supremum norm of 1 − p_{1}. That is, 6 · 10^{−9} is roughly the difference of p_{1} from being constant.

1.5. Other Related Work. Isoperimetric problem on the torus equipped with Haar measure have been studied in several places including [CS06, Ros01], though many problems are unresolved here. Any relation of the present work to [CS06, Ros01] is unclear, since the measures under consideration are different.

Different isoperimetric problems exhibiting “crystallization” (or the optimality of sets consisting of parallel stripes) have been studied in, e.g. [The06, BPT13, GM12, GS16, DR19], though these studies have typically focused only on n = 2 or n = 3.

2. Poisson Summation Formula

We recall some standard facts about the Poisson Summation formula.

Lemma 2.1 (Poisson Summation Formula, [Ste70, p. 252]). Let f: ℝ^{n} → ℝ be a C^{∞} function such that |f(x)| ≤ 100(1 + ∥x∥_{2})^{−2n} for all x ∈ ℝ^{n}. Define f̂(ξ) = F(f)(ξ) := ∫_{ℝ^{n}} f(x)e^{−2πi⟨x,ξ⟩}dx, ∀ ξ ∈ ℝ^{n}. Let α > 0. Then

∑_{z∈(αℤ)^{n}} f(y + z) = α^{−n} ∑_{w∈(ℤ/α)^{n}} f̂(w)e^{2πi⟨y,w⟩}, ∀ y ∈ ℝ^{n}.

Lemma 2.2 (Eigenfunction of the Fourier Transform, [SS03, p. 173]). ∀ x ∈ ℝ, define

h_{0}(x) := e^{−πx^{2}}.

Then

ĥ_{0}(y) = h_{0}(y), ∀ y ∈ ℝ.

Using the identity { \atop h(·/λ)}(y) = λĥ(λy), with λ = 1/\sqrt{2π}, we get

Lemma 2.3. For any y ∈ ℝ,

\frac{1}{\sqrt{2π}} e^{−y^{2}/2} = F[e^{−2π^{2}x^{2}}](y).

Combining Lemmas 2.1, 2.2 and 2.3,

Lemma 2.4. ∀ x ∈ ℝ,

∑_{z∈ℤ} γ_{1}(x + z) = ∑_{z∈ℤ} e^{−2π^{2}z^{2}}e^{2πixz} = 1 + ∑_{k=1}^{∞} 2e^{−2π^{2}k^{2}} cos(2πxk).

3. Weak Version of Isoperimetric Conjecture

We denote the periodization p_{n}(x) of the Gaussian density by

p_{n}(x) := ∑_{z∈ℤ^{n}} γ_{n}(x + z),  ∀ x ∈ ℝ^{n}.  (5)

We first note that p_{n} is a product measure. This follows directly from the definition of p_{n}.

Lemma 3.1. Let x = (x_{1}, …, x_{n}) ∈ ℝ^{n}. Then

p_{n}(x) = ∏_{i=1}^{n} p_{1}(x_{i}).

We now note that p_{1} is remarkably close to the constant function 1.

Lemma 3.2. Let x_{1} ∈ ℝ. Then

|1 − p_{1}(x_{1})| ≤ 54 · 10^{−10}, ∀ x_{1} ∈ ℝ.

Proof. Using Lemma 2.4 and an integral comparison,

|p_{1}(x_{1}) − 1| =^{(5)} | ∑_{z∈ℤ} γ_{1}(x_{1} + z) − 1| ≤ 2 ∑_{k=1}^{∞} e^{−2π^{2}k^{2}} = 2(e^{−2π^{2}} + e^{−8π^{2}}) + 2 ∑_{k=3}^{∞} e^{−2π^{2}k^{2}}

≤ 2(e^{−2π^{2}} + e^{−8π^{2}}) + 2 ∫_{2}^{∞} e^{−2π^{2}y^{2}}dy ≤ 2(e^{−2π^{2}} + e^{−8π^{2}}) + 2 ∫_{2}^{∞} ye^{−2π^{2}y^{2}}dy

= 2(e^{−2π^{2}} + e^{−8π^{2}}) + π^{−2}e^{−8π^{2}} ≤ 54 · 10^{−10}.
□

Combining Lemmas 3.1 and 2.4 proves the Main Theorem, Theorem 1.10.

Proof of Theorem 1.10. ∀ 1 ≤ i ≤ n, let v_{i} ∈ ℝ^{n} be the vector with a 1 in its i^{th} coordinate and a 0 in all other coordinates. Let Π_{i}: [0, 1]^{n} → [0, 1]^{n} be the projection onto the facet of the cube perpendicular to the i^{th} coordinate, so that Π_{i}(x) = x − ⟨x, v_{i}⟩v_{i} for all x ∈ [0, 1]^{n}. Since Ω is periodic , Definition 1.6 implies that

Π_{i}([0, 1]^{n} ∩ ∂Ω) = Π_{i}([0, 1]^{n}),  ∀ 1 ≤ i ≤ n.  (6)

We first consider the case that ∂Ω consists of a finite number of flat polyhedral facets. If F ⊆ [0, 1]^{n} is one such facet, and if N(x) is a unit normal vector at x ∈ F, then Lemmas 3.1 and 3.2 together with the Cauchy projection formula (or the coordinate definition of a surface integral) imply

∫_{F} |⟨N(x), v_{i}⟩| p_{n}(x)dx = ∫_{F} |⟨N(x), v_{i}⟩| ∏_{j=1}^{n} p_{1}(x_{j})dx

≥ (1 − 54 · 10^{−10}) ∫_{F} |⟨N(x), v_{i}⟩| ∏_{j: j≠i} p_{1}(x_{j})dx

= (1 − 54 · 10^{−10}) ∫_{Π_{i}(F)} ∏_{j: j≠i} p_{1}(x_{j})dx.

Summing over 1 ≤ i ≤ n, we get

∫_{F} ∥N(x)∥_{1} p_{n}(x)dx ≥ (1 − 54 · 10^{−10}) ∑_{i=1}^{n} ∫_{Π_{i}(F)} ∏_{j: j≠i} p_{1}(x_{j})dx.

By approximating an arbitrary C^{∞} manifold ∂Ω by a set of flat polyhedral faces, we get

∫_{[0,1]^{n}∩∂Ω} ∥N(x)∥_{1} p_{n}(x)dx ≥ (1 − 54 · 10^{−10}) ∑_{i=1}^{n} ∫_{Π_{i}([0,1]^{n}∩∂Ω)} ∏_{j: j≠i} p_{1}(x_{j})dx.  (7)

Then, using (6), we get

∫_{[0,1]^{n}∩∂Ω} ∥N(x)∥_{1} p_{n}(x)dx ≥ (1 − 54 · 10^{−10}) ∑_{i=1}^{n} ∫_{Π_{i}([0,1]^{n})} ∏_{j: j≠i} p_{1}(x_{j})dx

= (1 − 54 · 10^{−10})n ∏_{i=1}^{n−1} ∫_{0}^{1} p_{1}(x_{1})dx_{1} = (1 − 54 · 10^{−10})n.

In the last line, we used Lemma 2.4 (or just the definition (5) of p_{1}), which implies that ∫_{0}^{1} p_{1}(x_{1})dx_{1} = 1. Adding and subtracting the same term, we get

\sqrt{n} ∫_{[0,1]^{n}∩∂Ω} p_{n}(x)dx + ∫_{[0,1]^{n}∩∂Ω}(∥N(x)∥_{1} − \sqrt{n})p_{n}(x)dx ≥ (1 − 54 · 10^{−10})n.

Dividing by \sqrt{n} and using ∫_{∂Ω} γ_{n}(x)dx =^{(5)} ∫_{[0,1]^{n}∩∂Ω} p_{n}(x)dx,

∫_{∂Ω} γ_{n}(x)dx ≥ (1 − 54 · 10^{−10})\sqrt{n} + ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} ) γ_{n}(x)dx.

Then (3) follows since ∫_{∂B} γ_{n}(x)dx = ∑_{z∈(ℤ/\sqrt{n})} γ_{1}(z) = \sqrt{n} ∑_{w∈(\sqrt{n} ℤ)} e^{−2π^{2}w^{2}} by rotating ∂B so that all of its hyperplanes are perpendicular to the x_{1}-axis, using Lemma 2.1, and using n ≥ 2. Also, ∥N(x)∥_{1} ≤ \sqrt{n} for all x ∈ ∂Ω, so (4) follows from (3). □

Remark 3.3. The “robustness” term in Theorem 1.10 can be improved in the following way. Equation (7) can be improved so that it counts multiple preimages of Π_{i}([0, 1]^{n} ∩ Ω). For any 1 ≤ i ≤ n and for any x ∈ ∂Ω, let |Π_{i}^{−1}Π_{i}(x)| denote the number of preimages of Π_{i}(x) under Π_{i}. Then (7) can be improved to

∫_{[0,1]^{n}∩∂Ω} ∑_{i=1}^{n} \frac{|(N(x))_{i}|}{|Π_{i}^{−1}Π_{i}(x)|}p_{n}(x)dx ≥ (1 − 54 · 10^{−10}) ∑_{i=1}^{n} ∫_{Π_{i}([0,1]^{n}∩∂Ω)} ∏_{j: j≠i} p_{1}(x_{j})dx.

This leads to the following improvement in Theorem 1.10:

∫_{∂Ω} γ_{n}(x)dx ≥ (1 − 6 · 10^{−9}) ∫_{∂B} γ_{n}(x)dx + ∫_{∂Ω} (1 − ∑_{i=1}^{n} \frac{|(N(x))_{i}|}{\sqrt{n}|Π_{i}^{−1}Π_{i}(x)|})γ_{n}(x)dx.

Remark 3.4. The only properties of p_{n} used in the proof of Theorem 1.10 are Lemmas 3.1 and 3.2, i.e. that p_{n} is a product of one-dimensional probability measures, and each product term is close to 1. For example, one can replace the Gaussian measure with Lebesgue measure and prove the following similar (sharp) inequality: for any periodic set Ω ⊆ ℝ^{n},

∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} dx ≥ ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂B} dx + ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )dx.

Remark 3.5. Let Ω be a periodic set. Applying the divergence theorem to the vector field −\frac{p_{n}(x)}{π\sqrt{n}}∇ sin(π(x_{1} + ⋯ + x_{n})), we get

− ∫_{[0,1]^{n}∩∂Ω} \frac{∑_{i=1}^{n}(N(x))_{i}}{\sqrt{n}} cos(π(x_{1} + ⋯ + x_{n}))p_{n}(x)dx

= π\sqrt{n} ∫_{[0,1]^{n}∩Ω} (sin(π(x_{1} + ⋯ + x_{n})) − (\frac{∑_{i=1}^{n} \frac{∂}{∂x_{i}} p_{n}(x)}{\sqrt{n} p_{n}(x)}) cos(π(x_{1} + ⋯ + x_{n}))) p_{n}(x)dx.

The integral of the cos term is bounded in absolute value by 10^{−7}\sqrt{n} by Lemmas 3.1 and 3.2. In the case that Ω = {x ∈ ℝ^{n}: sin(π(x_{1} + ⋯ + x_{n})) ≥ 0}, we then get

|∫_{[0,1]^{n}∩∂Ω} \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} γ_{n}(x)dx − π\sqrt{n} ∫_{[0,1]^{n}∩Ω} sin(π(x_{1} + ⋯ + x_{n}))γ_{n}(x)dx| ≤ 10^{−7}\sqrt{n}.

So, if Ω is close to a periodic half space, then the “robustness” term ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & _{1} \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx in Theorem 1.10 and Corollary 1.11 measures how close Ω is to a periodic half space.

4. Weak Versions of Noise Stability Conjecture

Theorem 1.10 implies a similar statement for noise stability from Definition 1.5 with parameters 0 < ρ < 1 that are close to 1, using routine methods, if some smoothness is assumed for the boundary of Ω ⊆ ℝ^{n}.

In this section, when Ω ⊆ ℝ^{n}, we denote

f := 1_{Ω} : ℝ^{n} → ℝ.

Lemma 4.1 ([Kan11, Proof of Lemma 3.1]). Let d > 0. Let g: ℝ^{n} → ℝ be a degree d polynomial. Let Ω = {x ∈ ℝ^{n}: g(x) ≥ 0}. Let X, Y ∈ ℝ^{n} be independent standard Gaussian random vectors. Let ε > 0. Then

ℙ(f(X) = 1, f(X + εY) = 0) = \frac{ε}{\sqrt{2π}} ∫_{∂Ω} γ_{n}(x)dx + o(ε).

Here and below, the implied constant o(ε) can depend on g.

Lemma 4.2 ([Kan11, Lemma 3.4]). Let d > 0. Let g: ℝ^{n} → ℝ be a degree d polynomial. Let Ω = {x ∈ ℝ^{n}: g(x) ≥ 0}. Let X, Y ∈ ℝ^{n} be independent standard Gaussian random vectors. Let ε > 0. Then

ℙ(f(X) ≠ f(X(1 + ε))) ≤ dε\sqrt{\frac{n}{4π}} .

Lemma 4.3. Let d > 0. Let g: ℝ^{n} → ℝ be a degree d polynomial. Let Ω = {x ∈ ℝ^{n}: g(x) ≥ 0}. Let X, Y ∈ ℝ^{n} be independent standard Gaussian random vectors. Let 0 < η < 1/2. Then

ℙ(X ∈ Ω, X\sqrt{1 − η^{2}} + ηY ∈ Ω) = γ_{n}(Ω) − \frac{η}{\sqrt{2π}} ∫_{∂Ω} γ_{n}(x)dx + o(η).

Here and below, the implied constant o(η) can depend on g.

Proof. Let Z := X\sqrt{1 − η^{2}} + ηY, and let r := 1/\sqrt{1 − η^{2}}. Using the identity ℙ(A_{1}) = ℙ(A_{1} ∩ A_{2}) + ℙ(A_{1} ∩ A_{2}^{c}) for events A_{1}, A_{2},

\begin{aligned}ℙ(f(X) = 1, f(Z) = 1) & = ℙ(f(X) = 1, f(Z) = 1, f(Z) = f(rZ)) \\ & + ℙ(f(X) = 1, f(Z) = 1, f(Z) ≠ f(rZ)). \end{aligned}  (8)

We apply Lemma 4.2 to the second term of (8) with ε := (1 − η^{2})^{−1/2} − 1 to get

ℙ(f(X) = 1, f(Z) = 1, f(Z) ≠ f(rZ)) ≤ ℙ(f(Z) ≠ f(rZ)) ≤ dη^{2}\sqrt{n}.

And the first term of (8) is equal to

ℙ(f(X) = 1, f(rZ) = 1, f(Z) = f(rZ)) = ℙ(f(X) = 1, f(rZ) = 1)
− ℙ(f(X) = 1, f(rZ) = 1, f(Z) ≠ f(rZ)).

Using Lemma 4.2 again, the last quantity is at most dη^{2}\sqrt{n}, while

ℙ(f(X) = 1, f(rZ) = 1) = ℙ(f(X) = 1) − ℙ(f(X) = 1, f(rZ) = 0)

= γ_{n}(Ω) − \frac{η}{\sqrt{2π}} ∫_{∂Ω} γ_{n}(x)dx + o(η).

In the last line we used Lemma 4.1. Combining the above estimates gives

ℙ(X ∈ Ω, X\sqrt{1 − η^{2}} + ηY ∈ Ω) = ℙ(f(X) = 1, f(Z) = 1)

= γ_{n}(Ω) − \frac{η}{\sqrt{2π}} ∫_{∂Ω} γ_{n}(x)dx + o(η).

□

Proof of Corollary 1.11. Let η := \sqrt{1 − ρ^{2}}. From Lemma 4.3,

ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω) ≤ γ_{n}(Ω) − \begin{matrix}√ & \overline{1 − ρ^{2}} \\ √ & \overline{2π} \end{matrix} ∫_{∂Ω} γ_{n}(x)dx + o(\sqrt{1 − ρ^{2}}).

Since Ω is periodic , Ω^{c} = −Ω, so γ_{n}(Ω) = 1/2. Applying Theorem 1.10 gives

ℙ(X ∈ Ω, ρX + Y \sqrt{1 − ρ^{2}} ∈ Ω)

≤ \frac{1}{2} − \begin{matrix}√ & \overline{1 − ρ^{2}} \\ √ & \overline{2π} \end{matrix} ((1 − 6 · 10^{−9}) ∫_{∂B} γ_{n}(x)dx + ∫_{∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )γ_{n}(x)dx) + o(\sqrt{1 − ρ^{2}}).

Finally, applying Lemma 4.3 to B completes the proof. □

By repeating the proof of Lemma 4.1, we get the following. For completeness, we provide a proof with a dimension-dependent implied constant.

Lemma 4.4. Let Ω ⊆ ℝ^{n} be a periodic set. Assume that ∂Ω is a C^{∞} manifold. Let X, Y ∈ ℝ^{n} be independent random variables such that X is uniformly distributed in [−\frac{1}{2}, \frac{1}{2}]^{n} and Y is a standard Gaussian random vectors. Let ε > 0. Then

ℙ(f(X) = 1, f(X + εY) = 0) = \frac{ε}{\sqrt{2π}} ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} dx + o(ε).

Proof. For any s > 0, x ∈ ℝ^{n}, and for any f: ℝ^{n} → [0, 1], let U_{s}f(x) := ∫_{ℝ^{n}} f(x + y\sqrt{2s})γ_{n}(y)dy. Let Δ := ∑_{i=1}^{n} ∂^{2}/∂x_{i}^{2}. It is well known that (d/ds)U_{s}f(x) = ΔU_{s}f(x) for all s > 0, x ∈ ℝ^{n}. Using the divergence theorem,

\frac{d}{ds} ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩Ω} U_{s}1_{Ω^{c}}(x)dx = ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩Ω} ΔU_{s}1_{Ω^{c}}(x)dx = ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩Ω} div(∇U_{s}1_{Ω^{c}}(x))dx

= ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω}⟨∇U_{s}1_{Ω^{c}}(x), N(x)⟩dx + ∫_{(Ω∩∂[− \frac{1}{2} , \frac{1}{2} ]^{n})\∂Ω}⟨∇U_{s}1_{Ω^{c}}(x), N(x)⟩dx.

(9)

Changing variables and differentiating,

∇U_{s}1_{Ω^{c}}(x) = \frac{1}{\sqrt{2s}} ∫_{ℝ^{n}} y1_{Ω^{c}}(x + y\sqrt{2s})γ_{n}(y)dy, ∀ x ∈ ℝ^{n}.

Therefore, lim_{s→0^{+}} 2\sqrt{πs} ∇U_{s}1_{Ω^{c}}(x) = N(x) for all x ∈ ∂Ω. That is,

∇U_{s}1_{Ω^{c}}(x) = \frac{1}{2\sqrt{πs}}N(x) + o(s^{−1/2}),  ∀ x ∈ ∂Ω.  (10)

Also, lim_{s→0^{+}} 2\sqrt{πs} ∇U_{s}1_{Ω^{c}}(x) = 0 for all x ∉ ∂Ω. So, using f = 1_{Ω},

ℙ(f(X) = 1, f(X + εY) = 0) = ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩Ω} U_{ε^{2}/2}1_{Ω^{c}}(x)dx

= ∫_{s=0}^{s=ε^{2}/2} \frac{d}{ds}( ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩Ω} U_{s}1_{Ω^{c}}(x)dx)ds

=^{(9)∧(10)} ( ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} dx) ∫_{s=0}^{s=ε^{2}/2} (\frac{1}{2\sqrt{πs}} + o(s^{−1/2}))ds = \frac{ε}{\sqrt{2π}} ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} dx + o(ε).

□

Proof of Corollary 1.15. Note that ℙ(X ∈ Ω) = 1/2 since −Ω = Ω^{c}. Using Lemma 4.4,

ℙ(X ∈ Ω, X + εY ∈ Ω) = ℙ(X ∈ Ω) − ℙ(X ∈ Ω, X + εY ∉ Ω)

= \frac{1}{2} − \frac{ε}{\sqrt{2π}} ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} dx + o(ε).

So, by Remark 3.4 and Lemma 4.4 applied to B,

ℙ(X ∈ Ω, X + εY ∈ Ω) ≤ \frac{1}{2} − \frac{ε}{\sqrt{2π}} ( ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂B} 1 + (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )dx) + o(ε)

= ℙ(X ∈ B, X + εY ∈ B) − ∫_{[− \frac{1}{2} , \frac{1}{2} ]^{n}∩∂Ω} (1 − \begin{matrix}∥N(x)∥ & 1 \\ √ & \overline{n} \end{matrix} )dx + o(ε).

□

Acknowledgement. Thanks to Elchanan Mossel and Joe Neeman for helpful discussions, especially concerning the “robustness” term in the main results.

References

[ABS10] Sanjeev Arora, Boaz Barak, and David Steurer, Subexponential algorithms for unique games and related problems, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science FOCS 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 563–572. MR 3025231

[AKKT15] Naman Agarwal, Guy Kindler, Alexandra Kolla, and Luca Trevisan, Unique games on the hypercube, Chicago J. Theor. Comput. Sci. 2015 (2015).

[BBH^{+}12] Boaz Barak, Fernando G. S. L. Brandão, Aram Wettroth Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou, Hypercontractivity, sum-of-squares proofs, and their applications, Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, 2012, pp. 307–326.

[BKS19] Boaz Barak, Pravesh K. Kothari, and David Steurer, Small-set expansion in shortcode graph and the 2-to-2 conjecture, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, 2019, pp. 9:1–9:12.

[Bor75] Christer Borell, The Brunn-Minkowski inequality in Gauss space, Invent. Math. 30 (1975), no. 2, 207–216. MR 0399402 (53 #3246)

[Bor85] , Geometric bounds on the Ornstein-Uhlenbeck velocity process, Z. Wahrsch. Verw. Gebiete 70 (1985), no. 1, 1–13. MR 795785 (87k:60103)

[BPT13] DP Bourne, MA Peletier, and F Theil, Optimality of the triangular lattice for a particle system with wasserstein interaction, To appear in Communications in Mathematical Physics (2013).

[BS01] A. Burchard and M. Schmuckenschlger, Comparison theorems for exit times, Geometric & Functional Analysis GAFA 11 (2001), no. 4, 651–692 (English).

[CS06] Rustum Choksi and Peter Sternberg, Periodic phase separation: the periodic cahn-hilliard and isoperimetric problems, Interfaces and Free Boundaries 8 (2006), no. 3, 371–392.

[DKK^{+}18] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra, On non-optimally expanding sets in grassmann graphs, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, 2018, pp. 940–951.

[DMN17] Anindya De, Elchanan Mossel, and Joe Neeman, Noise stability is computable and approximately low-dimensional, 32nd Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 79, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pp. Art. No. 10, 11. MR 3691135

[DR19] Sara Daneri and Eris Runa, Exact periodic stripes for minimizers of a local/nonlocal interaction functional in general dimension, Archive for Rational Mechanics and Analysis 231 (2019), no. 1, 519–589.

[Eld15] Ronen Eldan, A two-sided estimate for the gaussian noise stability deficit, Inventiones mathematicae 201 (2015), no. 2, 561–624 (English).

[GM12] Alessandro Giuliani and Stefan Müller, Striped periodic minimizers of a two-dimensional model for martensitic phase transitions, Communications in Mathematical Physics 309 (2012), no. 2, 313–339.

[GS16] Alessandro Giuliani and Robert Seiringer, Periodic striped ground states in ising models with competing interactions, Communications in Mathematical Physics 347 (2016), no. 3, 983–1007.

[HNW19] Aram W. Harrow, Anand Natarajan, and Xiaodi Wu, Limitations of semidefinite programs for separable states and entangled games, Communications in Mathematical Physics (2019).

[Kan11] Daniel M. Kane, The gaussian surface area and noise sensitivity of degree-d polynomial threshold functions, computational complexity 20 (2011), no. 2, 389–412.

[Kho02] Subhash Khot, On the power of unique 2-prover 1-round games, Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (New York), ACM, 2002, pp. 767–775 (electronic). MR MR2121525

[Kho10] , On the unique games conjecture, 25th Annual IEEE Conference on Computational Complexity—CCC 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 99–121. MR 2932348 [KKMO07] Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell, Optimal inapproximability

results for MAX-CUT and other 2-variable CSPs?, SIAM J. Comput. 37 (2007), no. 1, 319–357. MR 2306295 (2008d:68035)

[KM16] Subhash Khot and Dana Moshkovitz, Candidate hard unique game, Proceedings of the Fortyeighth Annual ACM Symposium on Theory of Computing, STOC ’16, ACM, 2016.

[KMMS18] Subhash Khot, Dor Minzer, Dana Moshkovitz, and Muli Safra, Small set expansion in the johnson graph, Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 78.

[KMS17] Subhash Khot, Dor Minzer, and Muli Safra, On independent sets, 2-to-2 games, and grassmann graphs, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 2017, pp. 576–589.

[KMS18] , Pseudorandom sets in grassmann graph have near-perfect expansion, Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 6.

[Led96] Michel Ledoux, Isoperimetry and Gaussian analysis, Lectures on probability theory and statistics (Saint-Flour, 1994), Lecture Notes in Math., vol. 1648, Springer, Berlin, 1996, pp. 165–294. MR 1600888 (99h:60002)

[MN15] Elchanan Mossel and Joe Neeman, Robust optimality of Gaussian noise stability, J. Eur. Math. Soc. (JEMS) 17 (2015), no. 2, 433–482. MR 3317748

[MOO10] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), no. 1, 295–341. MR 2630040 (2012a:60091)

[Ros01] Antonio Ros, The isoperimetric problem, Proceedings from the Clay Mathematics Institute Summer School, MSRI, Berkeley, CA, 2001, Available at http://www.ugr.es/∼aros/isoper.pdf.

[RST12] Prasad Raghavendra, David Steurer, and Madhur Tulsiani, Reductions between expansion problems, Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC) (Washington, DC, USA), CCC ’12, IEEE Computer Society, 2012, pp. 64–73.

[SC74] V. N. Sudakov and B. S. Cirel′son, Extremal properties of half-spaces for spherically invariant measures, Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 41 (1974), 14–24, 165, Problems in the theory of probability distributions, II. MR 0365680 (51 #1932)

[SS03] Elias M. Stein and Rami Shakarchi, Fourier analysis, Princeton Lectures in Analysis, vol. 1, Princeton University Press, Princeton, NJ, 2003, An introduction. MR 1970295

[Ste70] Elias M. Stein, Singular integrals and differentiability properties of functions, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, N.J., 1970. MR 0290095 (44 #7280)

[The06] Florian Theil, A proof of crystallization in two dimensions, Communications in Mathematical Physics 262 (2006), no. 1, 209–236.

Department of Mathematics, UCLA, Los Angeles, CA 90095-1555

Department of Mathematics, University of Notre Dame, Notre Dame, IN 46656

E-mail address: sheilman@nd.edu