Leslie Ann Goldberg
  • Professor Leslie Ann Goldberg

  • Direct Email: leslie.goldberg@seh.ox.ac.uk
  • Alternative Email: leslie.goldberg@cs.ox.ac.uk
  • Office: 330 Wolfson Building

  • Address: Department of Computer Science, University of Oxford,
    Wolfson Bldg, Parks Rd,
    Oxford OX1 3QD United Kingdom

New! 4-year postdoctoral position working with me at Oxford: We are advertising a postdoctoral position in Algorithms and Complexity Theory working with me at the University of Oxford. The job is available for four years starting from 1 Oct 2021. The closing date is 12 noon on Friday 26 March 2021. The job advertisement (with the link for applications) is here. Please feel free to email me with any questions.

I am a Professor of Computer Science and head of the Algorithms and Complexity Theory Reseach Theme at the University of Oxford and a Senior Research Fellow at St Edmund Hall.

I am on sabbatical for the period Jan-Sept 2021 (though I will still serve as REF Coordinator for Computer Science and Informatics during this period, so feel free to continue to contact me about that).

When I return at the start of Oct 2021, I will serve as the Head of Department and will resume teaching the MSc and Part C course Probability and Computing.

Research Interests

I am interested in the design and analysis of randomised algorithms and in the probabilistic analysis of algorithms. Many important randomised algorithms are based on simulating Markov chains and other stochastic processes. Key research questions include determining how long a Markov chain must be simulated before it reaches a distribution which is close to its stationary distribution, determining convergence rates of other stochastic processes, and using these convergence rates to obtain algorithmic performance guarantees. Examples of this work include

"Spin systems" are statistical physics models in which there is an underlying graph and in each "configuration" every vertex is assigned a "spin" (which you can think of as a positive integer from some fixed range). The local interactions between the spins (caused by the edges of the graph) give rise to the global "energy", or weight, of a configuration. Computational problems including sampling configurations with probabilities proportional to their weights, and estimating the "partition function", which is the sum of the weights of all configurations. Here is a recent example of work applying Markov-chain techniques to these problems.

The problem of estimating the partition function of a spin system gives rise to foundational complexity-theoretic problems. Such a spin system is typically characterised by several parameters. For some values of the parameters, it is possible to build good sampling and estimation algorithms. For some other values of the parameters, it is possible to prove that such good algorithms do not exist, subject to complexity-theoretic conjectures similar to the famous "P not equal to NP" conjecture. This leads to a fundamental classification problem - determining for which parameter-values good algorithms exist, and for which there are provably no good algorithms. Examples of this work include

The problem of estimating a partition fuctions can be viewed as a generalisation of a computational problem in which the goal is to count combinatorial structures. A key example is #BIS, the problem of counting the independent sets of a bipartite graph. The following paper with Martin Dyer, Catherine Greenhill and Mark Jerrum introduced this problem and showed that it is complete in a large complexity class for approximate counting. We now know that #BIS is equivalent in difficulty to a large number of other computational problems, so it would be wonderful to resolve the question of whether it has a fast approximation algorithm.