Leslie Ann Goldberg
Professor
Leslie Ann
Goldberg
Professor of Computer Science
Senior Research Fellow,
St Edmund Hall
leslie.goldberg@cs.ox.ac.uk
+44 (0)1865 610755
Room 255, Wolfson Building, Parks Road, Oxford OX1 3QD 
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 NPcomplete. 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 wellstructured that dichotomy theorems are possible  within these wide classes, it can be shown that every problem is either in P, or is NPcomplete.
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
I am a Professor of Computer Science at Oxford University and a Senior Research Fellow at St Edmund Hall.
I grew up in Los Alamos, New Mexico (friends from there know me as "Leslie Henderson"). From 19831987 I was a student at Rice University in Houston, Texas. From 19871992 I was a student at the University of Edinburgh, in Scotland. From 19921995 I worked in the Algorithms and Discrete Math Department at Sandia Labs in New Mexico. From 19952006 I worked at the University of Warwick, in Coventry. From 20062013 I worked at the University of Liverpool.
Links
Personal Webpage (including publications)
Info
Themes 

Activities 
Algorithms At Large  Constraints Group  Computational Complexity  Core Algorithms 
Projects 

Completed Projects 

Current Student 
