The Classification Program of Counting Complexity

# click the upper-left icon to select videos from the playlist

source: Simons Institute    2016年4月4日
The Classification Program of Counting Complexity
Mar. 28 – Apr. 1, 2016
Recent years have seen dramatic progress in counting complexity. In exact computation, we now have a complete classification of counting CSPs into those that are polynomial-time solvable and those that are hard for the complexity class #P. The past decade or so has also seen the emergence of a nascent complexity theory of approximate counting.
The aim of this workshop is to spur progress in this field. In exact computation, we would like to extend our study into models that are more general than CSPs or more refined (e.g., holants, also known as tensor networks, or as factor graphs). We will also examine the algorithmic effectiveness of classification criteria. For problems that are computationally intractable, we need to examine escape routes. Recent dichotomy theorems strongly suggest that holographic algorithms based on matchgates are a universal methodology for problems that are #P-hard in general but P-time computable over planar structures. This thesis is subject to refutation by on-going work. For approximate computation, the corresponding complexity theory is provisional, leaving several important problems unclassified, and needs to be developed. Where efficient approximation algorithms in the conventional sense do not exist, we should look for algorithms that provide weaker approximation guarantees, for example bounding the logarithm of the number of solutions.
The ultimate goal of this investigation is to shed light on the computational complexity of counting problems from domains such as the following: graph homomorphisms, constraint satisfaction problems, holants, combinatorial enumeration problems (generating functions), models from statistical physics (partition functions), graph polynomials and polynomials on more general structures.
For more information, please visit https://simons.berkeley.edu/workshops/counting2016-2.
These presentations were supported in part by an award from the Simons Foundation.

Approximately Counting Graph Homomorphisms 47:37 Leslie Ann Goldberg, University of Oxford https://simons.berkeley.edu/talks/les...
Spin Systems: Hardness of Approximate Counting via Phase Transitions 46:31
Approximating 2-State Spin Systems 42:54
Counting in Sparse Classes of Structures 45:08
Fine-Grained Complexity Classification of Counting Problems 30:56
On the Power of Holographic Algorithms with Matchgates 48:16
Basis Collapse for Holographic Algorithms Over all Domain Sizes 44:44
Approximation Algorithms for Partition Functions of Edge-Coloring Models 49:22
Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs 39:35
Counting Matrix Partitions of Graphs 45:08
How to Not Prove Two Important Theorems 41:31
The Computational Complexity of Counting List H-Colourings, and Related Problems 47:02
Towards Understanding the Complexity of the Ising Partition Function 46:04
The Complexity of Computing Averages 42:33
The Complexity of Approximating Small Degree Boolean #CSP 33:59
Canonical Paths for MCMC: From Art to Science 39:41
Dichotomies for Counting Subgraphs 46:27
Counting Approximation Complexity Classification Through Clones and Invariants 47:20
Enumerator Polynomials: Completeness and Intermediate Complexity 47:42
Dichotomy Theorems for Generalized Chromatic Polynomials 46:53
Geometric Perspectives on Problems in Complexity Theory 46:35
Categories, Representations, and Counting Complexity 44:25
Hilbert's Nullstellensatz Certificates of Infeasibility for Combinatorial Problems 38:34
Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property 45:12
LP Relaxations for Valued CSPs 40:48
Counting with Bounded Treewidth 40:38