Computational Complexity of Counting and Sampling

ISBN-13: 9781138035577 / Angielski / Miękka / 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 will consist 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