István Miklós

Approximating with Markov chains

Counting problems are natural counterparts of decision problems, which ask the number of solutions instead of their existence. Counting problems are usually harder than their decision problem counterparts, indeed, in many cases the counting problem is #P-complete even if the decision problem is solvable in polynomial time.

An interesting observation in the last 20 years was that many #P-complete counting problems have a stochastic approximation algorithm using Markov chains. These Markov chains converge quickly to the uniform distribution over the solution space, hence allow an almost uniform generation of solutions. This almost uniform generation yield an fpras (fully polynomial randomized approximation scheme) for finding the cardinality of the solution space. In the first half of the talk, I will give an overview of the developed techniques, theorems, and achieved results.

In the second half of the talk, I will present a novel idea how to construct quickly mixing Markov chains, some results and a bounch of open problems.