MathDB

Standard simplex conjecture, bilinear positive-correlation version

Let m≥3m\geq 3 and 0<ρ<10<\rho<1. Consider two measurable partitions Ω1,…,Ωm\Omega_1,\ldots,\Omega_m and Ω1′,…,Ωm′\Omega'_1,\ldots,\Omega'_m of Rn+1\mathbb{R}^{n+1} with γn+1(Ωi)=γn+1(Ωi′)\gamma_{n+1}(\Omega_i)=\gamma_{n+1}(\Omega'_i) for every ii, and minimize the bilinear Gaussian noise-stability sum subject to these constraints. Standard simplex conjecture, bilinear positive-correlation version. If m−1≤n+1m-1\leq n+1, then for vertices z1,…,zmz_1,\ldots,z_m of a regular simplex in Rn+1\mathbb{R}^{n+1} centered at the origin, every minimizer satisfies

Ωi=−Ωi′={x∈Rn+1:⟨x,zi⟩=max⁡1≤j≤m⟨x,zj⟩}\Omega_i=-\Omega'_i=\{x\in\mathbb{R}^{n+1}:\langle x,z_i\rangle=\max_{1\leq j\leq m}\langle x,z_j\rangle\}

for all ii. This bilinear formulation is designed to capture the negative-correlation minimization problem; even the two-candidate case has applications in communication complexity, while the general assertion remains open.

Sources & referencesView supporting material

Primary source

Steven Heilman, “Hyperstable Sets with Voting and Algorithmic Hardness Applications”, arXiv:2209.11216 (2022).

Additional references

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

communication-complexitygaussian-isoperimetrynoise-stability

Progress summary

Refreshed
Partially solved

A paper gives structural reductions and a conditional characterization of optimizers, but the conjecture itself remains open.

The conjecture predicts that, when the number of parts is no larger than the ambient dimension plus two, every optimizer is given by opposite regular-simplex cones. No source identifies an original proposer or gives a complete proof.

Known results

  • A minimizer exists for the bilinear problem (Lemma 7.3).
  • Under m≤n+2m\leq n+2, every minimizer reduces, up to rotation and null sets, to a partition in Rm−1\mathbb{R}^{m-1} (Theorem 7.9).
  • If the minimizing partitions are hyperstable, they are congruent regular simplicial cones; this is conditional, not a proof of the conjecture.
  • The associated negative-correlation and hardness consequences are likewise conditional.

Current status (as of August 2026): The conjecture remains open; existence and dimension-reduction results are known, and the regular-simplex conclusion is proved only under the additional hyperstability assumption.

Sources

Solutions 0

No solutions have been posted yet.