The relative complexity of approximate counting problems
by
Catherine Greenhill
University of Melbourne
Coauthors: Martin Dyer (University of Leeds), Leslie Goldberg (University of Warwick), Mark Jerrum (University of Edinburgh)

Not much is known about the complexity of obtaining approximate solutions to counting problems. A few problems are known to admit an efficient approximation algorithm, or "FPRAS". Some others are known not to admit an FPRAS (under reasonable complexity-theoretic assumptions). The notion of approximation-preserving reduction is introduced in order to examine the relative complexity of approximate counting problems. As well as the two classes of interreducible problems described above (the "easiest"

and "hardest" problems) an interesting third class emerges, of apparently intermediate complexity. I will give an overview of some of these results, as well as a flavour of the methods used to prove them.

Date received: October 1, 2000