Social choice, computational complexity, Gaussian geometry, and Boolean functions
From MaRDI portal
Publication:4589022
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.
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
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
- scientific article; zbMATH DE number 2156838 (Why is no real title available?)
- 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)
