Research Information

Publications

• Collision of random walks and a refined analysis of attacks on the discrete logarithm problem.
        S. Kijima and R. Montenegro.
        Proceedings of Public-Key Cryptography 2015 (PKC 2015), Springer LNCS 9020, pp. 127-149 (2015).

• Groups of rotating squares.
        R. Montenegro, D. Huckaby, and E.White-Harmon.
        Journal of Combinatorial Mathematics and Combinatorial Computing (to appear).
  

• Intersection conductance and canonical alternating paths, methods for general finite Markov chains.
  (also, slides from a talk at the Random Structures & Algorithms 2011 Conference).
        R. Montenegro.
        Combinatorics, Probability, and Computing, vol. 23:4, pp. 585-606 (July 2014).
  

• A Birthday Paradox for Markov chains, with an optimal bound for collision in the Pollard Rho Algorithm for Discrete Logarithm.
  (also, video of a talk I gave at the Newton Institute of Cambridge University).
        J.-H. Kim, R. Montenegro, Y. Peres and P. Tetali.
        The Annals of Applied Probability, vol. 20:2, pp. 295-521 (2010).
        Preliminary version in Proc. of the Algorithmic Number Theory Symposium (ANTS-VIII), Springer LNCS 5011, pp. 402-415 (2008).

• How long does it take to catch a wild kangaroo? (submitted)
        R. Montenegro and P. Tetali.
        Preliminary version in Proc. of 41st ACM Symposium on Theory of Computing (STOC 2009), pp. 553-559 (2009).
  
  • The French science magazine La Recherche had an article about my paper (March 2009, pp. 29).
  • Alexander Frieden made an online version of the related Kruskal count card trick.
  • The card trick motif can be used to demonstrate the Kangaroo method itself.

• The simple random walk and max-degree walk on a directed graph.
        R. Montenegro.
        Random Structures & Algorithms, volume 34:3, pp. 395-407 (2009).

• Sharp edge, vertex, and mixed Cheeger inequalities for finite Markov kernels.
  (also, video of a talk I gave at MSRI in Berkeley.)
        R. Montenegro.
        Electronic Communications in Probability, volume 12, pp. 377-389 (2007).

• Near Optimal Bounds for Collision in Pollard Rho for Discrete Log.
        J.-H. Kim, R. Montenegro, and P. Tetali.
        IEEE Proc. of the Symposium on Foundations of Computer Science (FOCS 2007), pp. 215-223 (2007).

• Mathematical Aspects of Mixing Times in Markov Chains.
        R. Montenegro and P. Tetali.
        Book in series Foundations and Trends in Theoretical Computer Science (ed: M. Sudan), volume 1:3, NOW Publishers, Boston-Delft (June 2006).

• Blocking conductance and mixing in random walks.
        R. Kannan, L. Lovász, and R. Montenegro.
        Combinatorics, Probability and Computing, volume 15:4, pp. 541-570 (2006).

• A sharp isoperimetric bound for convex bodies.
        R. Montenegro.
        Israel Journal of Mathematics, volume 153, pp. 267-284 (2006).

• Mixing Time bounds via the Spectral Profile.
        S. Goel, R. Montenegro and P. Tetali.
        Electronic Journal of Probability, volume 11, pp. 1-26 (2006).

• Vertex and edge expansion properties for rapid mixing.
        R. Montenegro.
        Random Structures & Algorithms, volume 26:1-2, pp. 52-68 (2005).

• Rapid Mixing of Several Markov Chains for a Hard-Core Model.
        R. Kannan, M. Mahoney and R. Montenegro.
        Proc. of the Symposium on Algorithms and Computation (ISAAC 2003), Springer LCS2906, pp. 663-675 (2003).

• Edge Isoperimetry and Rapid Mixing on Matroids and Geometric Markov Chains.
        R. Montenegro and J-B. Son.
        Proc. of 33rd ACM Symposium on Theory of Computing (STOC 2001), pp. 704-711 (2001).

Other Write-ups

• Duality and evolving set bounds on mixing times.
  This survey is an in-depth development of the theoretical aspects of the method of Evolving Sets, a method which has been used in several of my papers. It is fairly esoteric as to a large degree it stems from my efforts to ascertain whether Evolving sets is provably stronger than other isoperimetric methods (answer: yes, with qualifications). For an introduction to the method please see Chapter 4 of my book with Prasad Tetali (PDF available above) or the paper of Morris and Peres.

• Math 8843 - Convergence of Markov Chains.
  These are notes for a graduate course on Convergence of Markov chains I taught in Fall 2004 at Georgia Tech. The previous term Dana Randall taught a related undergraduate course, so in this class we focused on theory and advanced methods. Lectures 8-21 covers material on Log-Sobolev, Nash Inequalities, and Evolving Sets; this is better learnt from my book with Prasad Tetali (PDF available above) in which we develop more elegant arguments than what was available at the time of this course.

• My Ph.D. Dissertation.
  Most of the material in here appears in my published research, but Chapter 3 details a discrete version of Blocking Conductance which is not published elsewhere.