30 citations · 59 across the 12 of their papers we have counts for
6 papers · 1 filter
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…
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…