**Ravi Montenegro**Chair, Professor, GPS Math Coordinator

- CollegeKennedy College of Sciences
- DepartmentMathematical Science
- Phone(978) 934-2442
- OfficeSouthwick 303F
- Email

## 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