Skip to Main Content

Ravi Montenegro

Ravi Montenegro
Ravi R. MontenegroAssociate Professor

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

Awards and Honors

  • Postdoctoral Fellowship (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

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. (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 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