### Skapa referens, olika format (klipp och klistra)

**Harvard**

Isaksson, M. (2009) *Applications of Gaussian Noise Stability in Inapproximability and Social Choice Theory*. Göteborg : Chalmers University of Technology (Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University, nr: 2009:1).

** BibTeX **

@book{

Isaksson2009,

author={Isaksson, Marcus},

title={Applications of Gaussian Noise Stability in Inapproximability and Social Choice Theory},

abstract={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.},

publisher={Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers tekniska högskola,},

place={Göteborg},

year={2009},

series={Preprint - Department of Mathematical Sciences, Chalmers University of Technology and Göteborg University, no: 2009:1},

keywords={Gaussian noise stability, inapproximability theory, invariance principle, max-q-cut, condorcet voting},

note={83},

}

** RefWorks **

RT Dissertation/Thesis

SR Electronic

ID 85162

A1 Isaksson, Marcus

T1 Applications of Gaussian Noise Stability in Inapproximability and Social Choice Theory

YR 2009

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

PB Institutionen för matematiska vetenskaper, matematisk statistik, Chalmers tekniska högskola,

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

LA eng

LK http://www.math.chalmers.se/Math/Research/Preprints/2009/1.pdf

OL 30