Computational Complexity of Counting and Sampling

ISBN-13: 9781138070837 / Angielski / Twarda / 2019 / 390 str.

Istvan Miklos

Opis

The purpose of the book is to give a comprehensive and detailed introduction to the computational
complexity of counting and sampling. The book consists of three main topics: I. Counting problems that are solvable in polynomial running time, II. Approximation algorithms for counting and sampling, III. Holographic algorithms.

Spis treści

1. Background on computational complexity
2. Algebraic dynamic programming and monotone computations
3. Linear algebraic algorithms. The power of subtracting
4. #P-complete counting problems
5. Holographic algorithms
6. Methods of random generations
7. Mixing of Markov chains and their applications in the theory of
counting and sampling
8. Approximable counting and sampling problems