On the complexity of approximating partition functions

本项目属于EPSRC理论计算机科学研究领域。概述、目标和研究方法：本博士项目研究逼近某些配分函数的复杂性。这一领域最近一直是理论计算机科学顶级期刊和会议上发表的几篇论文的焦点，人们正在不断开发新的技术来设想有效的逼近算法或证明逼近的难易程度。配分函数起源于统计力学，描述热力学平衡系统的统计性质。这些系统通常经历相变，这意味着物理系统的性质在特定温度附近突然变化。有趣的是，在许多热力学中研究得很好的系统中，这种物理相变也被证明是一种计算相变，它决定了何时可以有效地近似系统的配分函数。在这一广泛的领域内，我们在以下两个方向进行了研究：逼近复值配分函数的复杂性，以及近似计算随机k-CNF公式满意赋值的高效马尔可夫链蒙特卡罗算法。本项目的第一个目标是开发技术，使我们能够分析复参数配分函数的计算复杂性。我们研究了Ising和Potts模型的配分函数，以及Tutte多项式。多年来(甚至几十年)，这些分区函数一直是许多出版物关注的焦点。由于难以确定近似问题的复杂性，大多数近似计数出版物将他们的注意力限制在真实参数上。然而，鉴于配分函数起源于统计力学，配分函数从一开始就被研究在非实参数上。我们利用复动力学和配分函数的零点之间的联系来解决非实参数的逼近问题。本课题的第二个目的是研究满足k-CNF公式(每个子句都有k个变量的合取范式的公式)赋值的一致抽样问题。这是我们领域中的一个基本问题，而且由于Cook-Levin定理，它在最坏的情况下是NP-困难的。最近有了显著的进展：当我们在所有n个变量和m个子句的公式中均匀地随机选择一个k-CNF公式时，如果m/n至多为2k/301且k足够大，则有一个多项式时间算法来逼近该公式的满意赋值个数，并且该算法对几乎所有的输入都是成功的。不幸的是，这个算法在实际中不太可能有任何帮助，因为运行时间的多项式在k中次指数。我们的目标是在这种情况下获得一个有效的算法，关键思想是应用成功的谱独立框架来分析某些马尔可夫链的混合时间。工作和合作者：1.逼近复值Potts模型的复杂性，Andreas Galanis，Leslie Ann Goldberg，AndréS Herrera-Poyatos，计算复杂性，2022.2。在有界度图上逼近复值伊辛模型的复杂性，Andreas Galanis，Leslie Ann Goldberg，AndréS Herrera-Poyatos，SIAM离散数学期刊，2022.3。随机k-SAT，Andreas Galanis，Leslie Ann Goldberg，Heng Guo，AndréS Herrera-Poyatos，Arxiv预印本，2022年满意作业的快速抽样。

This project falls within the EPSRC Theoretical Computer Science research area.Summary, aims and research methodology:This PhD project studies the complexity of approximating some partition functions. This area has recently been the focus of several publications in top journals and conferences in theoretical computer science, and new techniques to envisage efficient approximation algorithms or to prove hardness of approximation are constantly being developed. Partition functions arise in statistical mechanics and describe the statistical properties of a system in thermodynamic equilibrium. These systems typically undergo a phase transition, which means that the properties of the physical system change abruptly near a certain temperature. Interestingly, in many well-studied systems in thermodynamics, this physical phase transition turns out to also behave as a computational phase transition that determineswhen the partition function of the system can be efficiently approximated. Within this broad area, we have pursued research in the following two directions: the complexity of approximating complexvalued partition functions, and efficient Markov Chain Monte Carlo algorithms to approximately count satisfying assignments of random k-CNF formulas.The first aim of this project is developing techniques that allow us to analyse the computational complexity of partition functions on complex parameters. We study the partition functions of the Ising and Potts model, as well as the Tutte polynomial. These partition functions have been the focus of many publications over the years (and decades). Due to the difficulty of determining the complexity of the approximation problem, most approximate counting publications restrict their attention to real parameters. However, given their origin in statistical mechanics, partition functions were studied on non-real parameters since the very beginning. Here we exploit the connection between complex dynamics and zeros of partition functions to tackle the approximation problem on non-real parameters.The second aim of this project is studying the problem of uniformly sampling satisfying assignments of a k-CNF formula (a formula in conjunctive normal form such that each clause has k variables). This is a fundamental problem in our field, and it is NP-hard in the worst case thanks to Cook-Levin theorem. Recently there has been remarkable progress: when we choose a k-CNF formula uniformly at random among all formulas with n variables and m clauses, if m/n is at most 2k/301 and k is large enough, there is a polynomial-time algorithm to approximate the number of satisfying assignments of the formula, and this algorithm succeeds for almost all inputs. Unfortunately, this algorithm is unlikely to be of any help in practice as the polynomial in the running time has degree exponential in k. Our goal is obtaining an efficient algorithm in this setting, and the key idea is applying the successful spectral independence framework to analyse the mixing time of certain Markov chains.Work produced and collaborators:1. The complexity of approximating the complex-valued Potts model, Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos, Computational Complexity, 2022.2. The complexity of approximating the complex-valued Ising model on bounded degree graphs, Andreas Galanis, Leslie Ann Goldberg, and Andrés Herrera-Poyatos, SIAM Journal on Discrete Mathematics, 2022.3. Fast sampling of satisfying assignments from random k-SAT, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Andrés Herrera-Poyatos, arXiv preprint, 2022.