Department of Computer Science
University of Warwick
4pm Wednesday 15th May 2002
Room 2509, JCMB, King's Buildings
A goal within computational complexity is to understand the complexity of approximate counting problems. Lots of natural counting problems (for example, counting independent sets in graphs, counting 3-colourings, computing the partition function in various models from statistical physics) are #P-complete. This means that we are very unlikely to be able to solve them exactly in polynomial time. Some of these problems are easy to solve approximately, and others are more difficult --- we are just beginning to understand the structure of #P from the perspective of approximability. When we can do approximate counting, it is usually because we know how to sample the structures uniformly at random, and we know how to use these samples to estimate the size of the relevant set. In this talk I will discuss some issues related to the complexity of approximately counting and randomly sampling. The concrete problem that I will focus on is the "H-colouring problem". In this problem, H is a fixed graph and the goal is to count homomorphisms from an input graph G to H. Many natural problems (including all of the ones that I listed above) can be viewed as special cases of the H-colouring problem.