Professor Leslie Ann Goldberg

Senior Research Fellow and Professor of Computer Science

Leslie Ann Goldberg is a Senior Research Fellow at St Edmund Hall and Head of the Department of Computer Science. She is the head of the Algorithms and Complexity Theory Research Theme. Her research is in the mathematical foundations of the subject.

Leslie works primarily in the area of computational complexity, where the aim is to discover which computational problems are feasible, which are inherently infeasible, and how the parameters of these problems influence feasibility.

Leslie has been awarded an ERC Advanced Grant, which will allow her to focus 100% of her time, for five years from early 2014, on her research project “Mapping the Complexity of Counting”. In a computational counting problem, a numerical quantity (a weighted sum) is computed, either exactly or approximately. Examples include computing (or estimating) an integral, a probability, or the expectation of a random variable. These problems arise in applications from fields such as statistics, statistical physics, information theory, and machine learning. The overall objectives of the project are to map out the landscape of computational counting problems, determining which problems are tractable, and which are intractable (quantifying the extent of tractability), and to develop complexity characterisations elucidating the features that make counting problems tractable or intractable.

Leslie grew up in Los Alamos, New Mexico, USA. She received her BA from Rice University in 1987 and her PhD from the University of Edinburgh in 1992. Before coming to Oxford in the summer of 2013, Leslie worked as a Senior Member of Technical Staff in the Algorithms and Discrete Maths Department of Sandia National Laboratories in the USA and then as a Lecturer, Reader, and Professor at the Universities of Warwick and Liverpool.

Where next?


Undergraduate course page

View Subject

An introduction to research in Computational Complexity Theory

26 Jun 2019

View Post