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
Biography
Graduate Coordinator for Mathematical Sciences
Continuing Education Coordinator for Mathematical Sciences
Selected 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
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.
- Breilh, J., Branco Jefer, C., Castelman, B.I., Cherniack, M., Christiani, D.C., Cicolella, A., Cifuentes, E., Clapp, R., Cole, D.C., Corn, M., De Ben, S., Diaz, R., Egilman, D., Finkelstein, Y., Franco, G., Frank, A.L., Friedman, L., Gassert, T.H., Gochfeld, M., Greenberg, M., Hansen, E.S., Hay, A., Hogstedt, C., Huff, J., Joshi, T.K., Kriebel, D., Laborde, A., LaDou, J., Levenstein, C., Levin, S.M., Loewenson, R., Mikheev, M., Montenegro, R.R., Naidoo, R., Ozonoff, D., Partanen, T., Pendito, R.I., Povey, G., Richter, E.D., Robbins, A., Rodrigues Corrèa Filho, H., Rosenman, K.D., Samuels, S.W., Sousa, S.V., Schwartz, B.S., Siqueira, C.E., Soskolne, C.L., Spiegel, J., Stephens, C., Mansoureh, T., Takaro, T.K., Teitelbaum, D.T., Tickner, J., Tomatis, L., Victora, C., Waltner-Toews, D., Wedeen, R.P., Wegman, D., Wesseling, C., Wing, S., Yassi, A. (2005). Texaco and its consultants. (11:2 pp. 217-20). International journal of occupational and environmental health
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