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

本课题研究计算复杂性理论中的计数问题。将调查三个相关领域。(1)自旋系统的近似复杂性。希望在精确理解自旋系统的近似配分函数和不可近似配分函数之间的界限方面取得进展。(2)更好地理解约束满足问题（CSP）的二分定理，以及图同态和Holant问题等计数问题的相关框架。大致上，出现了两种类型的二分定理。一种类型非常明确，并提供了对可跟踪性标准的更深层次的理解。另一种类型是无限的，通常甚至不清楚可溯性标准是可确定的。第二种类型的优势在于，它目前在逻辑意义上具有更广泛的覆盖范围。本项目将研究各种可跟踪性准则之间的相互关系，其具体目标是证明任意固定区域上计数CSP问题的最一般复加权配分函数的可决定二分定理。(3)研究基于匹配门的大于2个域的全息算法。对于域大小为2和一般2 × 2矩阵线性群上的复数，匹配子的可实现性和变换理论已经有了很好的发展。但对于更一般的变换群，这是完全未被探索的。这个项目将尝试在更一般的群体中发展这一理论。一个具体的目标是证明在大于2的域尺寸上的问题的二分定理，该定理表明所有可处理的平面CSP问题都是由约束函数定义的，这些约束函数要么对一般CSP问题可处理，要么通过使用匹配门的FKT算法进行全息变换可处理。人们对全息算法的新概念产生了浓厚的兴趣（美国科学家杂志在2008年1 - 2月刊上有一篇关于这一发展的专题文章）。在什么是有效可计算的或近似的，什么不是有效可计算的之间有一个更清晰的描述，在计算机科学内外有着更广泛的影响。在计算机科学领域，人们对人工智能很感兴趣；大量的工作以图形模型为中心。这些是配分函数的一些形式。在计算机科学之外，统计物理学研究相变有着悠久的传统，任何可证明的相变与计算复杂性理论之间的联系都将引起人们的极大兴趣。除了研究生的训练，还有大量的计算实验在设计的减少，这可以吸引本科生的研究。

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.