30 citations · 59 across the 12 of their papers we have counts for
12 papers
Groups of rotating squares
Ravi Montenegro, David A. Huckaby, Elaine White Harmon
This paper discusses the permutations that are generated by rotating blocks of squares in a union of overlapping rectangles. It is found that the sing…
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…
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log
Jeong Han Kim, Ravi Montenegro, Prasad Tetali
We analyze a fairly standard idealization of Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision oc…
Intersection conductance and canonical alternating paths, methods for general finite Markov chains
Ravi Montenegro
We extend the conductance and canonical paths methods to the setting of general finite Markov chains, including non-reversible non-lazy walks. The new path method is used to show t…
The simple random walk and max-degree walk on a directed graph
Ravi Montenegro
We show bounds on total variation and mixing times, spectral gap and magnitudes of the complex valued eigenvalues of a general (non-reversible non-lazy) Markov chain w…