Combinatorics, Complexity and Complex Zeros of Partition Functions

离散优化和枚举问题通常是由各种实际问题引起的，计算上很困难，因为它们的目标是找到特定的结构，或在非常大的集合中估计这种结构的数量，其中直接搜索的成本高得令人望而却步。处理这类问题的一种方法在很大程度上是由统计物理学推动的，在于计算某个量(配分函数)，它反映了所考虑的结构的平均特征。该项目旨在设计高效的配分函数计算算法，这将导致在各种困难的计算问题中产生新的高效算法。所提出的计算配分函数的方法是基于感兴趣区域中所涉及的函数的复零点的缺失，并将开发新的方法来定位此类零点。应用包括在给定的图中寻找稠密的子图，在超图中的完美匹配，以及在各种困难问题中计算按其到所选解的距离指数加权的所有解。与统计物理学的联系，特别是与Lee-Yang相变理论的联系也将被探索。该奖项反映了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.