Download or read book Complexity Classification of Exact and Approximate Counting Problems written by and published by . This book was released on 2015 with total page 740 pages. Available in PDF, EPUB and Kindle. Book excerpt: We study the computational complexity of counting problems, such as computing the partition functions, in both the exact and approximate sense. In the first part of the dissertation, we classify exact counting problems. We show a dichotomy theorem for Holant problems defined by any set of symmetric complex-valued functions on Boolean variables in both general and planar graphs. Problems are classified into three classes: those that are P-time solvable over general graphs; those that are P-time solvable over planar graphs but #P-hard over general graphs; those that remain #P-hard over planar graphs. It has been shown that in many other contexts, holographic algorithms with matchgates capture all counting problems in the second class. A surprising result is that we found a new class of tractable problems in the same class, but cannot be captured by holographic algorithms with matchgates. In the course of proving this dichotomy theorem, we also classify parity Holant problems and #CSP defined by any set of symmetric complex-valued functions on Boolean variables. Then we focus on approximating partition functions of 2-spin systems, including the famous Ising model as a special case. We show a fully polynomial-time approximation scheme (FPTAS) for anti-ferromagnetic 2-spin systems up to the tree uniqueness threshold. There is no such algorithm beyond the threshold unless NP = RP [SS14]. We also generalize this hardness result to bipartite graphs, with the exception that the Ising model without fields is approximable in bipartite graphs. This hardness result helps to establish some new imapproximability results for ferromagnetic 2-spin systems [LLZ14a]. To complement those, we give near-optimal FPTAS in certain regions of ferromagnetic 2-spin systems. Furthermore, we go beyond non-negative real weights, and classify the computational complexity of the Ising model with complex weights. Using such results, we draw conclusions about strong simulation of certain quantum circuits.