Description
It is a natural task to count mathematical objects with a given
property. For example, we might want to count the k-regular graphs of
n vertices, the increasing sub-permutations of a given permutation,
the sequences of a given length from alphabet {a,b} that do not
contain the substring aba, etc. Modern statistics requires the random
generations of mathematical objects. For example, random Latin squares
are used in experimental designs. Random objects are also frequently
generated to estimate the background distribution for hypothesis
testing. It is a well-known phenomenon that counting and sampling of
mathematical objects usually have the same computational complexity,
that is, the same amount of running time of a computer program
performing these tasks.
The aim of the lecture is to give an overview of the computational
complexity of counting and sampling. The lecture will start with the
very basics like the Fibonacci series, then will gradually move to
advanced topics like perfect matchings in planar graphs or
division-free algorithms to compute the determinant to eventually
arrive to cutting-edge problems like holographic reductions or
#BIS-complete counting problems.
The lecture is based on the recently published book with the same
title: https://www.crcpress.com/Computational-Complexity-of-Counting-and-Sampling/Miklos/p/book/9781138035577