论文标题
具有投票和算法硬度应用程序的Hyperstable设置
Hyperstable Sets with Voting and Algorithmic Hardness Applications
论文作者
论文摘要
Euclidean set $ a $带有相关性$ρ$的噪声稳定性是$（x，y）\在a \ times a $中的概率，其中$ x，y $是标准的高斯随机向量，具有相关性$ρ\ in（0,1）$。众所周知，一组欧几里得的固定高斯体积最大化噪声稳定性必须是半空间。 为了将欧几里得空间分为$ m> 2 $的零件，每个高斯度量$ 1/m $，仍然未知是什么设定了最大化其噪声稳定性的总和。在这项工作中，我们将最大化噪声稳定性的分区分类为噪声稳定性相对于$ρ$的衍生物的关键点。我们称之为满足这些条件的分区。我们的假设是，最大化分区是令人难以置信的，我们证明： *多数的（条件）版本是最稳定的猜想，价格为$ 3 $或$ 4 $候选。 * a（条件）锋利的独特游戏硬度结果最大值$ m = 3 $或$ 4 $ * A（条件）版本的Khot和Naor的螺旋桨猜想，价格为4美元。 我们还表明，一个令人震惊的对称集必须是星形的。 对于欧几里得空间的分区分为$ m> 2美元的固定（但也许是不平等）的高斯措施的部分，只有在所有零件都具有高斯尺寸$ 1/m $的情况下，才能满足高估财产。因此，作为我们的主要贡献，我们已经确定了证明完整多元化的可能策略是最稳定的猜想，而全部尖锐的硬度是最大值-M切割的：为了证明这两种陈述，足以证明设置最大化噪声稳定性的设置是可以过度使用的。最后一点至关重要，因为任何复数的证据都是最稳定的猜想，必须使用特殊的属性将集合分为相等的度量，因为在不平等的措施案例中，猜想是错误的。
The noise stability of a Euclidean set $A$ with correlation $ρ$ is the probability that $(X,Y)\in A\times A$, where $X,Y$ are standard Gaussian random vectors with correlation $ρ\in(0,1)$. It is well-known that a Euclidean set of fixed Gaussian volume that maximizes noise stability must be a half space. For a partition of Euclidean space into $m>2$ parts each of Gaussian measure $1/m$, it is still unknown what sets maximize the sum of their noise stabilities. In this work, we classify partitions maximizing noise stability that are also critical points for the derivative of noise stability with respect to $ρ$. We call a partition satisfying these conditions hyperstable. Uner the assumption that a maximizing partition is hyperstable, we prove: * a (conditional) version of the Plurality is Stablest Conjecture for $3$ or $4$ candidates. * a (conditional) sharp Unique Games Hardness result for MAX-m-CUT for $m=3$ or $4$ * a (conditional) version of the Propeller Conjecture of Khot and Naor for $4$ sets. We also show that a symmetric set that is hyperstable must be star-shaped. For partitions of Euclidean space into $m>2$ parts of fixed (but perhaps unequal) Gaussian measure, the hyperstable property can only be satisfied when all of the parts have Gaussian measure $1/m$. So, as our main contribution, we have identified a possible strategy for proving the full Plurality is Stablest Conjecture and the full sharp hardness for MAX-m-CUT: to prove both statements, it suffices to show that sets maximizing noise stability are hyperstable. This last point is crucial since any proof of the Plurality is Stablest Conjecture must use a property that is special to partitions of sets into equal measures, since the conjecture is false in the unequal measure case.
