Leslie Ann Goldberg

Professor Leslie Ann Goldberg

Professor of Computer Science

Senior Research Fellow, St Edmund Hall

E: leslie.goldberg@cs.ox.ac.uk

T: +44 (0)1865 610755

Room 330, Wolfson Building, Parks Road, Oxford OX1 3QD
United Kingdom

Themes:

Algorithms and Complexity Theory

Completed Projects:

Computational Counting

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.

Biography

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. For more information, see Leslie's more detailed web page.