Leslie Ann Goldberg

I work on the design and analysis of randomised algorithms. Randomised algorithms arise in many computational contexts including communication and information spread in networks, analysing computational models from statistical physics (and other models where local interactions influence global structure), and learning. My research focuses on the rigorous, mathematical analysis of these algorithms - proving results about how long the algorithms take, and how accurate they are. I am also interested in related questions from computational complexity where the goal is to figure out which computational problems can be solved with fast (randomised) algorithms and which problems provably can't be solved with fast algorithms. This research is part of the Algorithms and Complexity Theory research theme at Oxford.