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

Applications of Gaussian Noise Stability in Inapproximability and Social Choice Theory

Marcus Isaksson (Institutionen för matematiska vetenskaper, matematisk statistik)
Göteborg : Chalmers University of Technology, 2009. - 83 s.

Gaussian isoperimetric results have recently played an important role in proving fundamental results in hardness of approximation in computer science and in the study of voting schemes in social choice theory. In this thesis we prove a generalization of a Gaussian isoperimetric result by Borell and show that it implies that the majority function is optimal in Condorcet voting in the sense that it maximizes the probability that there is a single candidate which the society prefers over all other candidates. We also show that a different Gaussian isoperimetric conjecture which can be viewed as a generalization of the ''Double Bubble'' theorem implies the Plurality is Stablest conjecture and also that the Frieze-Jerrum semidefinite programming based algorithm for MAX-q-CUT achieves the optimal approximation factor assuming the Unique Games Conjecture. Both applications crucially depend on the invariance principle of Mossel, O'Donnell and Oleszkiewicz which lets us rephrase questions about noise stability of low-influential discrete functions in terms of noise stability of functions on R^n under Gaussian measure. We prove a generalization of this invariance principle needed for our applications.

Nyckelord: Gaussian noise stability, inapproximability theory, invariance principle, max-q-cut, condorcet voting

Denna post skapades 2009-01-12.
CPL Pubid: 85162


Läs direkt!

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

Institutioner (Chalmers)

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


Annan matematik

Chalmers infrastruktur


Datum: 2009-02-04
Tid: 10:15
Lokal: Room Euler, Mathematical Sciences, Chalmers tvärgata 3, Göteborg
Opponent: Prof. Johan Håstad, KTH

Ingår i serie

Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University 2009:1