Expertise
Convergence rate of markov chains, combinatorics, isoperimetric inequalities
Research Interests
Convergence rate of markov chains, birthday attacks, combinatorics
I study the speed with which finite Markov chains approach their stationary distribution. Recent work has focused on the analysis of two early birthday attacks on problems related to cryptography: Pollard's Rho and Kangaroo methods for Discrete logarithm.
Education
- Ph D: Mathematics, (2002), Yale University - New Haven, Connecticut
Dissertation/Thesis Title: Isoperimetric inequalities for faster mixing of Markov chains - BS: Mathematics, (1995), California Institute of Technology - CA
Selected Awards and Honors
- Invitation Fellowship for Research in Japan (2013), Scholarship/Research - Japan Society for the Promotion of Science (JSPS)
- NSF-VIGRE Postdoctoral Fellow (2002), Scholarship/Research - NSF-VIGRE
- NSF-VIGRE Graduate Fellow (1999), Scholarship/Research - NSF-VIGRE
Selected Publications
- Montenegro, R.R., Huckaby, D.A., White Harmon, E. (2016). Groups of rotating squares. Journal of Combinatorial Mathematics and Combinatorial Computing,96 335.
- Montenegro, R.R., Kijima, S. (Kyushu University) (2015). Collision of Random Walks and a Refined Analysis of Attacks on the Discrete Logarithm Problem (pp. 127–149). Public-Key Cryptography (PKC 2015)
- Montenegro, R.R. (2014). Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains. Combinatorics, Probability and Computing,23(04) 585–606.
- Kim, J.H., Montenegro, R.R., Peres, Y., Tetali, P. (2010). A Birthday Paradox for Markov chains with an optimal bound for collision in the Pollard Rho algorithm for discrete logarithm. Annals of Applied Probability,20(2) 495-521.
- Montenegro, R.R. (2009). The simple random walk and max-degree walk on a directed graph. Random Structures and Algorithms,34(3) 395-407.
- Montenegro, R.R. (2007). Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels. Electronic Communications in Probability,12 377-389.
- Montenegro, R.R. (2006). A sharp isoperimetric bound for convex bodies. Israel Journal of Mathematics,153 267-284.
- Kannan, R., Lov�sz, L., Montenegro, R.R. (2006). Blocking conductance and mixing in random walks. Combinatorics Probability and Computing,15(4) 541-570.
- Montenegro, R.R., Tetali, P. (2006). Mathematical aspects of mixing times in Markov Chains. Foundations and Trends in Theoretical Computer Science,1(3) 237-354.
- Goel, S., Montenegro, R.R., Tetali, P. (2006). Mixing time bounds via the spectral profile. Electronic Journal of Probability,11 1-26.
- Montenegro, R.R. (2005). Vertex and edge expansion properties for rapid mixing. Random Structures and Algorithms,26(1-2) 52-68.
Selected Presentations
- A simple heuristic for precisely determining complexity of many Birthday attacks - Workshop on Computation and Phase Transitions, June 2012
- Conductance and canonical paths for directed non-lazy walks - 15th International Conference on Random Structures and Algorithms, June 2011 - Atlanta, GA
- On birthday attacks and catching kangaroos - Technical Committee on Theoretical Foundations of Computing, June 2010 - Tokyo, Japan
- Mixing times and new Cheeger inequalities for nite Markov chains - Discrete Mathematics Seminar, March 2010
- How long does it take to catch a wild kangaroo? - 41st Annual ACM Symposium on Theory of Computing, June 2009 - Bethesda, MD
- Analysis of Pollard's Rho and Kangaroo methods for discrete logarithm - Working group on Analysis of Markov Chains on Combinatorial and Statistical Mechanics Models, June 2009
- Mixing times, a birthday paradox for Markov chains, and the Pollard Rho algorithm for discrete logarithm - Program on Markov chain Monte Carlo methods in discrete algorithms, August 2008 - Hitachi City, Japan
- A birthday paradox for Markov chains, with an optimal bound for collision in Pollard Rho for discrete logarithm - Workshop on Markov Chain Monte Carlo Methods, March 2008
- A near optimal bound for Pollard's Rho to solve discrete log - 48th Annual IEEE Symposium on Foundations of Computer Science, October 2007 - Providence, RI
- A birthday paradox for Markov chains, with an optimal bound for collision in Pollard Rho for discrete logarithm - Mathematical Sciences Seminar, October 2007
- A near optimal bound for Pollard's Rho to solve discrete log - Joint Seminar in Math and Computer Science, April 2007
- Cheeger inequalities for eigenvalues of non-reversible Markov kernels - Statistics Seminar, October 2006
- An analysis of the Pollard Rho algorithm for discrete logarithm - Statistics working group seminar, October 2006
- Cheeger inequalities for eigen values of non-reversible random walks - Combinatorics Seminar, January 2006
- Mixing times and new Cheeger inequalities for nite Markov chains - Mathematics Seminar, March 2005
- Modified conductance and new Cheeger inequalities - Mathematical Sciences Research Institute Workshop on Markov Chains, January 2005 - Berkeley, CA
- Evolving set and Cheeger bounds on the top and bottom eigenvalues - Combinatorics Seminar, September 2004
- Rapid mixing of several Markov chains for a hard-core model - The 14th Annual International Symposium on Algorithms and Computation, December 2003 - Kyoto, Japan
- Vertices, edges, gradients and a grid walk - 11th International Conference on Random Structures & Algorithms, August 2003 - Poznan, Poland
- Markov chain methods for studying water and some partial rapid mixing result - Laboratory for Foundations of Computer Science Seminar, March 2003
- Studying random walks by graph vertex-edge expansion - Combinatorics Seminar, November 2002
- Markov chain methods for studying water and some partial rapid mixing result - CDSNS/ACE Brown Bag Lunch, October 2002
- Isoperimetric inequalities for approximate counting - Combinatorics Seminar, September 2002
- Edge isoperimetry and rapid mixing on matroids and geometric Markov chains - 33rd Annual ACM Symposium on theory of computing, July 2001 - Crete, Greece