42 citations · 147 across the 42 of their papers we have counts for
12 papers · 1 filter
A note on shifting distributions via Poisson races
Amir Yehudayoff
This expository note is about simulating a target distribution from observations of a proposal distribution . In the model suggested by Harsha, Jain, McAllester and Radhakri…
Random walks on regular trees can not be slowed down
Omer Angel, Jacob Richey, Yinon Spinka +1
A random walk on a regular tree (or any non-amenable graph) has positive speed. We ask whether such a walk can be slowed down by applying carefully chosen time-dependent permutatio…
Anti-concentration and the Exact Gap-Hamming Problem
Anup Rao, Amir Yehudayoff
We prove anti-concentration bounds for the inner product of two independent random vectors, and use these bounds to prove lower bounds in communication complexity. We show that if…
Anti-concentration in most directions
Anup Rao, Amir Yehudayoff
We prove anti-concentration bounds for the inner product of two independent random vectors. For example, we show that if are subsets of the cube with $|A| \cdot…
Grounded Lipschitz functions on trees are typically flat
Ron Peled, Wojciech Samotij, Amir Yehudayoff
A grounded M-Lipschitz function on a rooted d-ary tree is an integer-valued map on the vertices that changes by at most along edges and attains the value zero on the leaves. We stu…
Lipschitz Functions on Expanders are Typically Flat
Ron Peled, Wojciech Samotij, Amir Yehudayoff
This work studies the typical behavior of random integer-valued Lipschitz functions on expander graphs with sufficiently good expansion. We consider two families of functions: M-Li…