How long does it take to catch a wild kangaroo?
Prasad Tetali and his collaborator Ravi Montenegro (University of Massachussetts, Lowell) recently had their work on Pollard's Kangaroo algorithm profiled in the French journal La Recherche (a French "Scientific American"). The paper, which is titled "How long does it take to catch a wild kangaroo?" gives a tight analysis of Pollard's Kangaroo algorithm (from 1978) to solve the discrete logarithm problem in cyclic groups. The paper appears in this year's ACM Symposium on Theory of Computing and it is available on the arxiv at http://arxiv.org/abs/0812.0789.