Leslie Ann Goldberg
  • Professor Leslie Ann Goldberg
  • Professor of Computer Science, University of Oxford,
    Senior Research Fellow, St Edmund Hall

  • 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

Research Interests:

My main research interest is computational complexity, where the aim is to discover which computational problems are feasible, which are inherently infeasible, and why. It is known that if P and NP are different then there is an infinite hierarchy of different complexity classes which lie strictly between them. Thus, even if it is proved that P and NP are different, there will be problems in NP whose complexity is difficult to pin down because they are neither in P nor NP-complete. Fortunately, there are wide classes of NP, such as classes of constraint satisfaction problems, which are rich enough to include important problems arising in applications, but which are sufficiently well-structured that dichotomy theorems are possible - within these wide classes, it can be shown that every problem is either in P, or is NP-complete.

I am particularly interested in dichotomies arising in computational counting. Computational counting problems involve the computation of weighted sums. They arise in practical applications from diverse fields including statistics, statistical physics, information theory, coding, and machine learning.

Efficient algorithms for approximate counting often rely on the Markov Chain Monte Carlo method. These algorithms are based on simulations of Markov chains, and a key research question is how long the Markov chains must be simulated in order to achieve a distribution which is close to the stationary distribution of the chain. In general, I am interested in convergence rates of stochastic processes, and in algorithmic questions related to the generation of random samples, as well as in algorithmic questions related to counting.

See my publications or CV for more information.

Research Group:

Oxford's Algorithms and Complexity Theory Group (Head of Group)

Contention Resolution Notes

Contention Resolution Notes (Out of date. Last updated Oct 2000)

Oxford Algorithms Day

Oxford Algorithms Day took place on 15 April 2015. Details are available here.