Combinatorics, Complexity and Complex Zeros of Partition Functions

离散优化和枚举的问题，往往产生于各种实际问题，是计算困难的，因为他们的目标是找到一个特定的结构，或估计这样的结构在非常大的集合，其中直接搜索是昂贵的。处理这些问题的一种方法，在很大程度上是由统计物理学激发的，包括计算一定的量（配分函数），它反映了所考虑的结构的平均特征。该项目旨在设计计算配分函数的有效算法，从而在各种困难的计算问题中产生新的有效算法。拟议的计算配分函数的方法是基于所讨论的函数在感兴趣的域中不存在复零点，并将开发定位此类零点的新方法。应用包括在给定图中寻找稠密子图，超图中的完美匹配，以及在各种困难问题中计算所有解，按其到选定解的距离指数加权。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Problems of discrete optimization and enumeration, often arising from a variety of practical questions, are computationally hard because they aim to find a particular structure, or estimate the number of such structures in very large sets, where the direct search is prohibitively expensive. One way of handling such problems, motivated to a large extent by statistical physics, consists in computing a certain quantity (partition function), which reflects the average characteristics of the structures under consideration. The project aims to design efficient algorithms for computing partition functions, which would lead to new efficient algorithms in a variety of difficult computational problems.The proposed approach to computing partition functions is based on the absence of complex zeros of the function in question in the domain of interest, and new methods to locate such zeros will be developed. Applications include finding dense subgraphs in a given graph, perfect matchings in hypergraphs, and counting all solutions, exponentially weighted by their distance to a selected solution, in a variety of hard problems. Connections to statistical physics, in particular to the Lee-Yang theory of phase transition, will also be explored.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.