Social choice, computational complexity, Gaussian geometry, and Boolean functions

zbMATH Open1375.91074arXiv1407.7763MaRDI QIDQ4589022FDOQ4589022

Authors: Ryan O'Donnell 

Publication date: 6 November 2017

Abstract: We describe a web of connections between the following topics: the mathematical theory of voting and social choice; the computational complexity of the Maximum Cut problem; the Gaussian Isoperimetric Inequality and Borell's generalization thereof; the Hypercontractive Inequality of Bonami; and, the analysis of Boolean functions. A major theme is the technique of reducing inequalities about Gaussian functions to inequalities about Boolean functions f : {-1,1}^n -> {-1,1}, and then using induction on n to further reduce to inequalities about functions f : {-1,1} -> {-1,1}. We especially highlight De, Mossel, and Neeman's recent use of this technique to prove the Majority Is Stablest Theorem and Borell's Isoperimetric Inequality simultaneously.

Full work available at URL: https://arxiv.org/abs/1407.7763

Recommendations

• Maximally stable Gaussian partitions with discrete applications
• Noise stability of functions with low influences: invariance and optimality
• Gaussian bounds for noise correlation of functions
• Sharp thresholds for monotone non-Boolean functions and social choice theory
• Majority is stablest: discrete and SoS

zbMATH Keywords

computational complexityisoperimetrysocial choicehypercontractivitymax-cutanalysis of Boolean functionsmajority is stablestGaussian geometry

Mathematics Subject Classification ID

Gaussian processes (60G15) Social choice (91B14) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited In (5)

• On the computability of quasi-transitive binary social choice rules in an infinite society and the halting problem
• Three candidate plurality is stablest for small correlations
• Title not available (Why is that?)
• Phase transitions and noise sensitivity on the Poisson space via stopping sets and decision trees
• Sharp thresholds for monotone non-Boolean functions and social choice theory

This page was built for publication: Social choice, computational complexity, Gaussian geometry, and Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4589022)