Istvan Miklos

Computational Complexity of Counting and Sampling

• Gebundenes Buch

Produktbeschreibung

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.

Produktdetails

• Verlag: CRC Press
• Seitenzahl: 408
• Erscheinungstermin: 18. Februar 2019
• Englisch
• Abmessung: 234mm x 156mm x 24mm
• Gewicht: 748g
• ISBN-13: 9781138070837
• ISBN-10: 1138070831
• Artikelnr.: 55157458

Autorenporträt

István Miklós is a Hungarian mathematician and bioinformatician at the Rényi Institute in Budapest. He holds a Ph.D. from Eotvos University in Budapest. His research interests lie in theoretical and applied computer science and combinatorics, particularly in the study of Markov chain, Monte Carlo methods and in sampling and counting combinatorial objects appearing in applied mathematics. He has more than 50 peer-reviewed scientific papers.

Inhaltsangabe

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