AF: Small: Counting Problems, Holographic Algorithms and Dichotomy Theorems

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

This project studies counting problems in computational complexity theory. Three related areas will be investigated. (1) The approximate complexity on spin systems. It is hoped that progress will be made to understand precisely the boundary between approximable and inapproximable partition functions for spin systems. (2) To gain a much better understanding of the dichotomy theorems for Constraint Satisfaction Problems (CSP), and related frameworks of counting problems such as Graph Homomorphisms and Holant Problems. Roughly, there have emerged two types of dichotomy theorems. One type is very explicit and offers a deeper understanding of the tractability criterion. Another type is more infinitary, and often it is not even clear that the tractability criterion is decidable. The strength of the second type is that it currently has a broader coverage in a logical sense. This project will study the interrelationship between various tractability criteria, with the concrete goal of proving a decidable dichotomy theorem for the most general complex-weighted partition functions of counting CSP problems over an arbitrary fixed domain. (3) To study holographic algorithms based on matchgates for domain size greater than two. The realizability and transformation theory of matchgates have already been well developed for domain size two and over the general linear group of 2 by 2 matrices over the complex numbers. But for more general transformation groups this is completely unexplored. This project will attempt to develop the theory over more general groups. A concrete aim is to prove a dichotomy theorem for problems over domain size greater than two, which states that all tractable planar CSP problems are defined by constraint functions that are either tractable for general CSP problems or tractable by a holographic transformation followed by the FKT algorithm using matchgates. There has been strong interest in the novel concept of holographic algorithms (American Scientist magazine had a feature article on this development in the Jan-Feb issue of 2008.) A sharper delineation between what is efficiently computable, or approximable, and what is not has broader impact within computer science and beyond. Within computer science there is a lot of interest in AI; a substantial body of work is centered around graphic models. These are some forms of partition functions. Outside computer science, there is a long tradition in statistical physics to study phase transitions, and any provable link between that and computational complexity theory will be of great interest. In addition to graduate student training, there is also a significant amount of computational experimentation in the design of reductions, which could engage undergraduate students in research.