Combinatorics, Complexity and Complex Zeros of Partition Functions

点击翻译按钮获取中文摘要

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.