78 citations · 335 across the 44 of their papers we have counts for
5 papers · 1 filter
A log-Sobolev inequality for the multislice, with applications
Yuval Filmus, Ryan O'Donnell, Xinyu Wu
Let satisfy and let denote the "multislice" of all strings in having exactly coordinates eq…
Social choice, computational complexity, Gaussian geometry, and Boolean functions
Ryan O'Donnell
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 Gau…
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Itai Benjamini, Siu-On Chan, Ryan O'Donnell +2
In majority dynamics, agents located at the vertices of an undirected simple graph update their binary opinions synchronously by adopting those of the majority of their neighbors.…
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Elchanan Mossel, Ryan O'Donnell, Oded Regev +2
In this paper we study non-interactive correlation distillation (NICD), a generalization of the study of noise sensitivity of boolean functions. We extend the model to NICD on tree…
Coin flipping from a cosmic source: On error correction of truly random bits
Elchanan Mossel, Ryan O'Donnell
We study a problem related to coin flipping, coding theory, and noise sensitivity. Consider a source of truly random bits $x \in \bits^n$, and parties, who have noisy versions…