Maximally stable Gaussian partitions with discrete applications
Maximally stable Gaussian partitions with discrete applications
复制标题
具有离散应用的最大稳定高斯分区
DOI：
10.1007/s11856-011-0181-7
复制
发表时间：
2009
影响因子：
1
通讯作者：
Elchanan Mossel
中科院分区：
文献类型：
--
作者：
Marcus Isaksson;Elchanan Mossel
高斯噪声稳定性的结果最近发挥了重要作用，证明结果的硬度近似在计算机科学和社会选择中的投票计划的研究。我们证明了一个新的高斯噪声的稳定性结果推广的等周结果由Borell的热核和推导作为应用程序：在孔多塞投票的背景下，多数的最优性结果。关于低影响函数的“宇宙抛硬币”猜想的证明。孔多塞投票中多数的最优性结果。关于低影响函数的“宇宙抛硬币”猜想的证明。我们还讨论了一个高斯噪声稳定性猜想，它可以被看作是“双泡”定理的推广，并表明它意味着：“多元性是最稳定的猜想”的证明。在唯一对策猜想的假设下，MAX-q-CUT的Frieze-Jerrum SDP达到了最优逼近因子。“多元性是最稳定的猜想”的一个证明。在唯一对策猜想的假设下，MAX-q-CUT的Frieze-Jerrum SDP达到了最优逼近因子。
Gaussian noise stability results have recently played an important role in proving results in hardness of approximation in computer science and in the study of voting schemes in social choice. We prove a new Gaussian noise stability result generalizing an isoperimetric result by Borell on the heat kernel and derive as applications: An optimality result for majority in the context of Condorcet voting. A proof of a conjecture on “cosmic coin tossing” for low influence functions. An optimality result for majority in the context of Condorcet voting. A proof of a conjecture on “cosmic coin tossing” for low influence functions. We also discuss a Gaussian noise stability conjecture which may be viewed as a generalization of the “Double Bubble” theorem and show that it implies: A proof of the “Plurality is Stablest Conjecture”. That the Frieze-Jerrum SDP for MAX-q-CUT achieves the optimal approximation factor assuming the Unique Games Conjecture. A proof of the “Plurality is Stablest Conjecture”. That the Frieze-Jerrum SDP for MAX-q-CUT achieves the optimal approximation factor assuming the Unique Games Conjecture.