CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Maximally stable Gaussian partitions with discrete applications

Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik) ; E. Mossel
Israel Journal of Mathematics (0021-2172). Vol. 189 (2012), 1, p. 347-396.
[Artikel, refereegranskad vetenskaplig]

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. 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.

Nyckelord: cut, algorithms, oceedings, p307, oceedings, p146

Denna post skapades 2012-07-16.
CPL Pubid: 160509


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematisk statistik (2005-2016)



Chalmers infrastruktur