30 citations · 59 across the 12 of their papers we have counts for
7 papers · 1 filter
How long does it take to catch a wild kangaroo?
Ravi Montenegro, Prasad Tetali
We develop probabilistic tools for upper and lower bounding the expected time until two independent random walks on $\ZZ$ intersect each other. This leads to the first sharp analys…
A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm
Jeong Han Kim, Ravi Montenegro, Yuval Peres +1
We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discr…
Duality and evolving set bounds on mixing times
Ravi Montenegro
This survey is an in-depth development of the theoretical aspects of the method of Evolving Sets, a method which has been used in several of my papers. It is fairly esoteric as to…
Sharp edge, vertex, and mixed Cheeger type inequalities for finite Markov kernels
Ravi Montenegro
We show how the evolving set methodology of Morris and Peres can be used to show Cheeger inequalities for bounding the spectral gap of a finite Markov kernel. This leads to sharp v…
Eigenvalues of non-reversible Markov chains: their connection to mixing times
Ravi Montenegro
This paper originally showed a lower bound on mixing time for a non-reversible Markov chain in terms of its largest non-trivial eigenvalue, and used this to re-derive some generali…
Mixing Time Bounds via the Spectral Profile
Sharad Goel, Ravi Montenegro, Prasad Tetali
On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the s…