39 citations · 63 across the 4 of their papers we have counts for
4 papers
Every decision tree has an influential variable
Ryan O'Donnell, Michael Saks, Oded Schramm +1
We prove that for any decision tree calculating a boolean function , \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where is the probability that the…
Noise stability of functions with low influences: invariance and optimality
Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz
In this paper we study functions with low influences on product probability spaces. The analysis of boolean functions with low influences has become a central problem in discrete F…
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…