University of Oxford Logo University of OxfordDepartment of Computer Science - Home
On Facebook
Facebook
Follow us on twitter
Twitter
Linked in
Linked in
Flickr
Flickr
Google plus
Google plus
Digg
Digg
Pinterest
Pinterest
Stumble Upon
Stumble Upon

Leslie Ann Goldberg

Personal photo - 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 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

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 1983-1987 I was a student at Rice University in Houston, Texas. From 1987-1992 I was a student at the University of Edinburgh, in Scotland. From 1992-1995 I worked in the Algorithms and Discrete Math Department at Sandia Labs in New Mexico. From 1995-2006 I worked at the University of Warwick, in Coventry. From 2006-2013 I worked at the University of Liverpool.

Links

Personal Webpage (including publications)

Info

Themes

Activities

Projects

Completed Projects

Current Student

Manage publications

SHARE THIS: