This dissertation furthers a systematic study of the complexity classification of counting problems. A central goal of this study is to prove complexity classification theorems which state that every problem in some large class is either polynomial-time computable (tractable) or #P-hard. Such classification results are important as they tend to give a unified explanation for the tractability of certain counting problems and a reasonable basis for the conjecture that the remaining problems are inherently intractable. In this dissertation, we focus on the framework of Holant problems on Boolean variables, as well as other frameworks that are expressible as Holant problems, such as counting constraint satisfaction problems and counting Eulerian orientation problems. First, we prove a complexity dichotomy for Holant problems on the Boolean domain with arbitrary sets of real-valued constraint functions. It is proved that for every set F of real-valued constraint functions, Holant(F) is either tractable or #P-hard. The classification has an explicit criterion. This is a culmination of much research on this decade-long study, and it uses many previous results and techniques. On the other hand, to achieve the present result, many new tools were developed, and a novel connection with quantum information theory was built. In particular, two functions exhibiting intriguing and extraordinary closure properties are related to Bell states in quantum information theory. Dealing with these functions plays an important role in the proof. Then, we consider the complexity of Holant problems with respect to planar graphs, where physicists had discovered some remarkable algorithms, such as the FKT algorithm for counting planar perfecting matchings in polynomial time. For a basic case of Holant problems, called six-vertex models, we discover a new tractable class over planar graphs beyond the reach of the FKT algorithm. After carving out this new planar tractable class which had not been discovered for six-vertex models in the past six decades, we prove that everything else is #P-hard, even for the planar case. This leads to a complete complexity classification for planar six-vertex models. This result is the first substantive advance towards a planar Holant classification with asymmetric constraints. We hope this work can help us better understand a fundamental question in theoretical computer science: What does it mean for a computational counting problem to be easy or to be hard?

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.

Presents a novel form of a compendium that classifies an infinite number of problems by using a rule-based approach.

Complexity theory aims to understand and classify computational problems, especially decision problems, according to their inherent complexity. This book uses new techniques to expand the theory for use with counting problems. The authors present dichotomy classifications for broad classes of counting problems in the realm of P and NP. Classifications are proved for partition functions of spin systems, graph homomorphisms, constraint satisfaction problems, and Holant problems. The book assumes minimal prior knowledge of computational complexity theory, developing proof techniques as needed and gradually increasing the generality and abstraction of the theory. This volume presents the theory on the Boolean domain, and includes a thorough presentation of holographic algorithms, culminating in classifications of computational problems studied in exactly solvable models from statistical mechanics.

Many fundamental combinatorial problems, arising in such diverse fields as artificial intelligence, logic, graph theory, and linear algebra, can be formulated as Boolean constraint satisfaction problems (CSP). This book is devoted to the study of the complexity of such problems. The authors' goal is to develop a framework for classifying the complexity of Boolean CSP in a uniform way. In doing so, they bring out common themes underlying many concepts and results in both algorithms and complexity theory. The results and techniques presented here show that Boolean CSP provide an excellent framework for discovering and formally validating "global" inferences about the nature of computation.

This book constitutes the refereed proceedings of the 17th Annual International Conference on Computing and Combinatorics, held in Dallas, TX, USA, in August 2011. The 54 revised full papers presented were carefully reviewed and selected from 136 submissions. Topics covered are algorithms and data structures; algorithmic game theory and online algorithms; automata, languages, logic, and computability; combinatorics related to algorithms and complexity; complexity theory; computational learning theory and knowledge discovery; cryptography, reliability and security, and database theory; computational biology and bioinformatics; computational algebra, geometry, and number theory; graph drawing and information visualization; graph theory, communication networks, and optimization; parallel and distributed computing.