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 for more information.

Research Theme:

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

Brief CV:

Leslie Ann Goldberg is a Professor of Computer Science at the University of Oxford and a Fellow of St Edmund Hall, a college of the University of Oxford. Prior to this, she was a Professor in the Department of Computer Science, University of Liverpool, a Lecturer, Warwick Research Fellow, Senior Lecturer and Reader in the Department of Computer Science, University of Warwick, and a Research Fellow and Senior Member of Technical Staff in the Algorithms and Discrete Mathematics Department at Sandia Labs in New Mexico, USA.

Leslie holds a BA from Rice University and a PhD from the University of Edinburgh (winning the UK Distinguished Dissertations in Computer Science prize). Leslie is a member of Academia Europaea, and has four best-paper prizes from ICALP. She has served as PC chair of ICALP 2008 and RANDOM 2011 and has served on the Executive Committee of STOC 2013. She has served as an editor-in-chief of the Journal of Discrete Algorithms and on the editorial board of SIAM Journal on Computing (SICOMP), the ACM Transactions on Algorithms, the Journal of Algorithms, and the LMS Journal of Computation and Mathematics. She is a Vice President of the EATCS. Leslie's research has been funded by the US DOE Office of Scientific Computing, the EU, the EPSRC, and the ERC, including the ERC Advanced Grant Mapping the Complexity of Counting (MCC)

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.