**Ravi R. Montenegro**Associate Professor

**College**College of Sciences**Department**Mathematical Science**Phone**(978) 934-2442**Email**Ravi_Montenegro@uml.edu

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

Dissertation/Thesis Title:*Isoperimetric inequalities for faster mixing of Markov chains***BS: Mathematics**, (1995), California Institute of Technology - CA**MS: Mathematics**, (1973), University of Rhode Island -**BA: Mathematics**, (1971), St. Anselm College - Manchester, NH

## Awards and Honors

- 2015 Faculty Award for Teaching Excellence (2015)
*, Teaching - University of Massachusetts Lowell* - Postdoctoral Fellowship (2005)
*- 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* - Yale University Fellowship (1999)
*, Scholarship/Research - Yale University* - NSF Minority Graduate Fellowship (1998)
*, Scholarship/Research - NSF* - NSF Minority Graduate Fellowship (1995)
*, Scholarship/Research - NSF* - Caltech Robert A. Millikan Scholarship (1992)
*, Scholarship/Research - Caltech*

## Publications

**Montenegro, R.R.**, Huckaby, D.A., White Harmon, E. (2016) "Groups of rotating squares.,"*Journal of Combinatorial Mathematics and Combinatorial Computing*96: pp. 335- Kijima, S.,
**Montenegro, R.R.**(2015) "Collision of Random Walks and a Refined Analysis of Attacks on the Discrete Logarithm Problem,"*Springer*pp. 127–149 **Montenegro, R.R.**, Huckaby, D.A., Harmon, E.W. (2014) "Groups of rotating squares,"*arXiv preprint arXiv:1404.5455***Montenegro, R.R.**(2014) "Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains,"*Combinatorics, Probability and Computing*23:04 pp. 585–606**Montenegro, R.R.**, Tetali, P. (2014) "Kruskal’s Principle and Collision Time for Monotone Transitive Walks on the Integers,"**Montenegro, R.R.**(2012) "A simple method for precisely determining complexity of many Birthday attacks,"- 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 pp. 495-521 **Montenegro, R.R.**(2009) "The simple random walk and max-degree walk on a directed graph,"*Random Structures and Algorithms*34:3 pp. 395-407**Montenegro, R.R.**(2007) "Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels,"*Electronic Communications in Probability*12: pp. 377-389**Montenegro, R.R.**(2006) "A sharp isoperimetric bound for convex bodies,"*Israel Journal of Mathematics*153: pp. 267-284- Kannan, R., Lov?sz, L.,
**Montenegro, R.R.**(2006) "Blocking conductance and mixing in random walks,"*Combinatorics Probability and Computing*15:4 pp. 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 pp. 237-354- Goel, S.,
**Montenegro, R.R.**, Tetali, P. (2006) "Mixing time bounds via the spectral profile,"*Electronic Journal of Probability*11: pp. 1-26 **Montenegro, R.R.**(2005) "Vertex and edge expansion properties for rapid mixing,"*Random Structures and Algorithms*26:1-2 pp. 52-68

## 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 eigenvalues of non-reversible random walks
*- Combinatorics Seminar, January 2006* - Mixing times and new Cheeger inequalities for nite Markov chains
*- Mathematics Seminar, March 2005* - Modied 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

## Contracts, Fellowships, Grants and Sponsored Research

- PI: AF:Small: Barriers to eciency of algorithms based on nite Markov Chains (2010),
*Grant - NSF (Algorithmic Foundations)* - Co-PI: In-situ polymerization of low band gap polymers for solid state solar cells. (2009),
*Grant - NSF (Solar)* - PI: AF:Small: Properties of Markov Chains required in proof but not in practice (2009),
*Grant - NSF (Algorithmic Foundations)* - PI: CAREER: Properties of Markov Chains required in proof but not in practice (2009),
*Grant - NSF CAREER (Probability)* - PI: Properties of Markov Chains required in proof but not in practice (2009),
*Grant - NSA-AMS Young Investigators Grant* - PI: Better mathematical tools for analyzing nite Markov chains: Birthday problems, canonical paths, and decomposition (2008),
*Grant - NSF CAREER* - PI: Derandomized Birthday problems, canonical paths, and decomposition methods for studying finite Markov chains (2008),
*Grant - NSF (Probability)* - AOC:Stochastic models of urban dynamics: co-PI (2007),
*Grant - NSF BCS*