The author aims to classify the computational difficulty of these problems for various naturally occurring structures: the emphasis is on positive results that demonstrate the existence of efficient algorithms. At the heart of the monograph is a single algorithmic paradigm; simulate a Markov chain whose states are combinatorial structures. A major portion of the monograph is devoted to developing new mathematical tools for the analysis of algorithms of this kind. Among the applications presented are the first provably efficient algorithms for several important counting and generation problems. Further applications are summarized in an appendix.
This book will be of interest to researchers and graduate students in theoretical computer science, probability and statistics and theoretical physicists with an interest in Monte Carlo methods. It is a timely contribution to a fast moving field, with the immediacy and freshness of a new discovery.
