← All problems

The Standard Simplex Conjecture for Gaussian noise stability

17 years old · traced to

Let n≥2n\geq2, let ρ∈[−1,1]\rho\in[-1,1], and let 3≤k≤n+13\leq k\leq n+1. Let {Ai}i=1k\{A_i\}_{i=1}^k be a measurable partition of Rn\mathbb{R}^n, meaning that ⋃i=1kAi=Rn\bigcup_{i=1}^k A_i=\mathbb{R}^n and γn(Ai∩Aj)=0\gamma_n(A_i\cap A_j)=0 for i≠ji\ne j. For bounded measurable f ⁣:Rn→Rf\colon\mathbb{R}^n\to\mathbb{R}, define

Tρf(x)=∫Rnf(xρ+y1−ρ2) dγn(y),T_\rho f(x)=\int_{\mathbb{R}^n}f(x\rho+y\sqrt{1-\rho^2})\,d\gamma_n(y),

where γn\gamma_n is standard Gaussian measure. A partition is regular simplicial conical if its parts are the Voronoi regions of the vertices of a regular simplex centered at the origin. The Standard Simplex Conjecture. If ρ∈(0,1]\rho\in(0,1] and γn(Ai)=1/k\gamma_n(A_i)=1/k for every ii, then

J=∑i=1k∫Rn1Ai(x)Tρ(1Ai)(x) dγn(x)J=\sum_{i=1}^k\int_{\mathbb{R}^n}1_{A_i}(x)T_\rho(1_{A_i})(x)\,d\gamma_n(x)

is maximized by a regular simplicial conical partition. If ρ∈[−1,0)\rho\in[-1,0), with no restriction on the measures of the parts, then JJ is minimized by a regular simplicial conical partition. This conjecture describes the optimal Gaussian rounding scheme for MAX-kk-CUT and is known in the two-part case; the source states that it remains open for k≥4k\geq4 and for negative or sufficiently large positive ρ\rho.

References

2 papers in this index state this conjecture (2009–2012). The statement above is taken from the most recent of them; the others are arXiv:0903.3362.

Source: Steven Heilman, “Euclidean Partitions Optimizing Noise Stability”, arXiv:1211.7138 (2014).

Progress summary

Refreshed
Open

The conjecture is proved only in special cases, and no public source reports a proof or counterexample for the full problem.

The conjecture says that regular simplex partitions optimize Gaussian noise stability for equally sized parts under positive correlation, and minimize it under negative correlation. The full equal-measure problem and the negative-correlation problem remain unresolved.

Known results

  • The two-part case is known.
  • Heilman proved the k=3k=3 equal-measure case for n≥2n\geq2 and sufficiently small positive ρ\rho (2012).
  • Heilman established additional bounded-dimensional regimes, with the dimension bound depending on ρ\rho.
  • De, Mossel, and Neeman proved computable approximate low-dimensionality (2017), not exact optimality.

Unequal-measure result (2014)

Heilman, Mossel, and Neeman showed that shifted flat partitions can beat the standard simplex when prescribed part measures are unequal, for every k≥3k\geq3 and nonzero ρ\rho. This does not refute the equal-measure conjecture stated here.

Current status (as of November 2026): The two-part case and several restricted positive-noise regimes are settled, but the general conjecture, including k≥4k\geq4, negative ρ\rho, and sufficiently large positive ρ\rho, remains open.

Sources

Solutions 0

No solutions have been posted yet.