| Professor Leslie Ann
Goldberg Email:
L.A.Goldberg at liverpool.ac.uk
Department of Computer
Science University of Liverpool Ashton Building Liverpool L69 3BX United Kingdom Room 320 Ashton
Building phone: 0151 795 4255 (from
outside UK: +44 151 795 4255)
fax: 0151 795 4235
|
|
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.