Leslie Ann Goldberg's home page

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, unless the P=NP? question can be answered, there will be problems in NP whose precise complexity cannot be resolved. This situation has led to attempts to identify smaller classes of problems within NP where dichotomy results may hold: every problem is either in P or is NP-complete. A similar situation exists for counting problems. If P is not equal to #P, there is an infinite hierarchy in between and it is important to identify subclasses of #P where dichotomy results hold. A lot of work has been done on identifying counting dichotomies in the context of constraint satisfaction problems, homomorphism problems and partition function computation problems. These classes of problems do exhibit dichotomies, despite being rich enough to include many important problems from a wide variety of fields from statistical physics to AI. There are still many open problems.

Another topic that interests me is the study of randomised algorithms and the probabilistic analysis of algorithms. I am interested in algorithms for randomly sampling combinatorial structures. Often, such algorithms are based on Markov-chain simulation. Typically, we want to sample from the stationary distribution of the Markov chain, and the goal of the research is to determine how long you have to simulate the Markov chain before you are likely to be near the stationary distribution. The research also has a mathematical flavour --- the goal is to provide provable performance guarantees like "If you simulate the chain for O(n log n) steps and then take a sample, then the resulting distribution is close (in some well-defined sense) to the stationary distribution." Often the relevant combinatorial structures are colourings or spin-configurations. Sometimes the relevant combinatorial structures are unlabelled structures, which can be viewed as isomorphism classes.

I am interested in contention-resolution protocols for multiple-access channels such as Ethernets and Optical Networks. These protocols can typically be viewed as Markov chains, and we are interested in questions of stability. (Informally, when the protocol is run, does it build up an ever-increasing backlog of messages?)

Other (related) research interests include algorithmic questions related to counting and listing combinatorial structures and algorithmic game theory.

See my publications for more information.

Brief Biography: 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. I joined the University of Liverpool in August 2006.

Miscellaneous Links

Pictures