We shall present an algorithm that uses a small amount of space and
provably runs in expected optimal time (up to log factors) for the discrete
log problem on arbitrary abelian groups; this appears to be first such
formally analysed one. This is inspired by the classic Pollard Rho.
                                           
Our techniques show that navigating giant (i.e. exponential) sized graphs
(e.g. Cayley digraphs) using small (i.e. polynomial) space resources is
hard on average which in turn suggests a construction of collision-resistant
hash functions.

Joint research with J. Horwitz (Stanford).

Talk will be self-contained, almost!



BIOGRAPHY

I am interested in problems that are provably hard to solve on a typical
instance ( via Levin's average case NP-completeness) and issues related to
randomness, cryptography, number theory, coding theory & algebraic curves
and content protection. I am interested in algorithms that can be
rigorously analysed and offer advantages over the competition in  practice. 

After getting a master's degree in EE from Indian Institute of Science
Bangalore, I worked in complexity theory under Leonid A Levin; I was a
senior researcher in the Math and Cryptography group at what was then
Bell Communications research 90-97,  then I joined the Cryptography Research
group at Microsoft. I spend my spare time on my 7 year-old son, music,
movies, nature, physics and mathematics.