Maximally Stable Gaussian Partitions with Discrete Applications

Details Maximally Stable Gaussian Partitions with Discrete Applications Maximally Stable Gaussian Partitions with Discrete Applications

2009-03-19

arxiv.org/abs/0903.3362v3

Mathematics

Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Maximally Stable Gaussian Partitions with Discrete Applications does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Maximally Stable Gaussian Partitions with Discrete Applications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximally Stable Gaussian Partitions with Discrete Applications will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-648790