Other Pages
My Home Page
UML Math
GATech Math
Yale Math


Research Information
Publications

Collision of random walks and a refined analysis of attacks on the discrete logarithm problem.
S. Kijima and R. Montenegro.
Proceedings of PublicKey Cryptography 2015 (PKC 2015), Springer LNCS 9020, pp. 127149 (2015).

Groups of rotating squares.
R. Montenegro, D. Huckaby, and E.WhiteHarmon.
Journal of Combinatorial Mathematics and Combinatorial Computing (to appear).

Intersection conductance and canonical alternating paths, methods for general finite Markov chains.
(also, slides from a talk at the Random Structures & Algorithms 2011 Conference).
R. Montenegro.
Combinatorics, Probability, and Computing, vol. 23:4, pp. 585606 (July 2014).

A Birthday Paradox for Markov chains, with an optimal bound for collision in the Pollard Rho Algorithm for Discrete Logarithm.
(also, video of a talk I gave at the Newton Institute of Cambridge University).
J.H. Kim, R. Montenegro, Y. Peres and P. Tetali.
The Annals of Applied Probability, vol. 20:2, pp. 295521 (2010).
Preliminary version in Proc. of the Algorithmic Number Theory Symposium (ANTSVIII), Springer LNCS 5011, pp. 402415 (2008).

How long does it take to catch a wild kangaroo? (submitted)
R. Montenegro and P. Tetali.
Preliminary version in Proc. of 41st ACM Symposium on Theory of Computing (STOC 2009), pp. 553559 (2009).

The simple random walk and maxdegree walk on a directed graph.
R. Montenegro.
Random Structures & Algorithms, volume 34:3, pp. 395407 (2009).

Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels.
(also, video of a talk I gave at MSRI in Berkeley.)
R. Montenegro.
Electronic Communications in Probability, volume 12, pp. 377389 (2007).

Near Optimal Bounds for Collision in Pollard Rho for Discrete Log.
J.H. Kim, R. Montenegro, and P. Tetali.
IEEE Proc. of the Symposium on Foundations of Computer Science (FOCS 2007), pp. 215223 (2007).

Mathematical Aspects of Mixing Times in Markov Chains.
R. Montenegro and P. Tetali.
Book in series Foundations and Trends in Theoretical Computer Science (ed: M. Sudan), volume 1:3, NOW Publishers, BostonDelft (June 2006).

Blocking conductance and mixing in random walks.
R. Kannan, L. Lovász, and R. Montenegro.
Combinatorics, Probability and Computing, volume 15:4, pp. 541570 (2006).

A sharp isoperimetric bound for convex bodies.
R. Montenegro.
Israel Journal of Mathematics, volume 153, pp. 267284 (2006).

Mixing Time bounds via the Spectral Profile.
S. Goel, R. Montenegro and P. Tetali.
Electronic Journal of Probability, volume 11, pp. 126 (2006).

Vertex and edge expansion properties for rapid mixing.
R. Montenegro.
Random Structures & Algorithms, volume 26:12, pp. 5268 (2005).

Rapid Mixing of Several Markov Chains for a HardCore Model.
R. Kannan, M. Mahoney and R. Montenegro.
Proc. of the Symposium on Algorithms and Computation (ISAAC 2003),
Springer LCS2906, pp. 663675 (2003).

Edge Isoperimetry and Rapid Mixing on Matroids and Geometric Markov Chains.
R. Montenegro and JB. Son.
Proc. of 33rd ACM Symposium on Theory of Computing (STOC 2001),
pp. 704711 (2001).
Other Writeups

Duality and evolving set bounds on mixing times.
This survey is an indepth 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 a large degree it stems from my efforts to ascertain whether Evolving sets is provably stronger than other isoperimetric methods (answer: yes, with qualifications). For an introduction to the method please see Chapter 4 of my book with Prasad Tetali (PDF available above) or the paper of Morris and Peres.

Math 8843  Convergence of Markov Chains.
These are notes for a graduate course on Convergence of Markov chains I taught in Fall 2004 at Georgia Tech. The previous term Dana Randall taught a related undergraduate course, so in this class we focused on theory and advanced methods. Lectures 821 covers material on LogSobolev, Nash Inequalities, and Evolving Sets; this is better learnt from my book with Prasad Tetali (PDF available above) in which we develop more elegant arguments than what was available at the time of this course.

My Ph.D. Dissertation.
Most of the material in here appears in my published research, but Chapter 3 details a discrete version of Blocking Conductance which is not published elsewhere.
[My Home Page]
[UMass Lowell Math Department]
Ravi Montenegro (ravi_montenegro@uml.edu)
