603 citations · 1.6k across the 72 of their papers we have counts for
5 papers · 1 filter
Concentration of Markov chains with bounded moments
Assaf Naor, Shravas Rao, Oded Regev
Let be a finite state stationary Markov chain, and suppose that is a real-valued function on the state space. If is bounded, then Gillman's expande…
A Sharp Tail Bound for the Expander Random Sampler
Shravas Rao, Oded Regev
Consider an expander graph in which a fraction of the vertices are marked. A random walk starts at a uniform vertex and at each step continues to a random neighbor. Gillman sho…
A Counterexample to Monotonicity of Relative Mass in Random Walks
Oded Regev, Igor Shinkar
For a finite undirected graph , let denote the probability that a continuous-time random walk starting at vertex is in at time . In this note we…
An Inequality for Gaussians on Lattices
Oded Regev, Noah Stephens-Davidowitz
$ \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\lat}{\mathcal{L}} \newcommand{\ensuremath}[1]{#1} $We show that for any lattice $\lat \subseteq \R^n$ and vectors $\vec{x},…
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…