On the complexity of approximating partition functions

该项目属于EPSRC理论计算机科学研究领域。摘要、目的及研究方法：本博士课题研究某些配分函数近似的复杂性。这一领域最近已成为理论计算机科学顶级期刊和会议的几个出版物的焦点，并且正在不断开发新的技术来设想有效的近似算法或证明近似的硬度。配分函数出现在统计力学中，描述系统在热力学平衡状态下的统计性质。这些系统通常经历相变，这意味着物理系统的性质在接近某一温度时突然改变。有趣的是，在热力学中许多被充分研究的系统中，这种物理相变也表现为计算相变，它决定了系统的配分函数何时可以有效地近似。在这个广阔的领域内，我们在以下两个方向进行了研究：逼近复值配分函数的复杂性，以及有效的马尔可夫链蒙特卡罗算法来近似计数随机k-CNF公式的满足赋值。该项目的第一个目标是开发技术，使我们能够分析复杂参数上配分函数的计算复杂性。我们研究了Ising和Potts模型的配分函数，以及Tutte多项式。这些配分函数多年来（甚至几十年来）一直是许多出版物关注的焦点。由于难以确定近似问题的复杂性，大多数近似计数出版物将注意力限制在实际参数上。然而，由于配分函数起源于统计力学，从一开始就研究非实参数的配分函数。本文利用复动力学与配分函数零点之间的联系来解决非实参数的逼近问题。这个项目的第二个目标是研究k- cnf公式（一种合取范式的公式，每个子句有k个变量）的一致采样满足赋值的问题。这是我们这个领域的一个基本问题，在最坏的情况下，由于库克-莱文定理，它是np困难的。最近有了显著的进展：当我们在所有有n个变量和m个子句的k- cnf公式中均匀随机选择一个k- cnf公式时，如果m/n不超过2k/301且k足够大，则存在一个多项式时间算法来近似该公式的满意赋值个数，并且该算法对几乎所有输入都是成功的。不幸的是，该算法在实际中不太可能有任何帮助，因为运行时间的多项式在k中具有指数度。我们的目标是在这种情况下获得一个有效的算法，关键思想是应用成功的谱无关框架来分析某些马尔可夫链的混合时间。制作的作品和合作者：近似复值波茨模型的复杂性，Andreas Galanis, Leslie Ann Goldberg, andr<s:1> Herrera-Poyatos，《计算复杂性》，2022.2。刘建军，刘建军，刘建军，等。有界度图上的复值Ising模型的逼近复杂性，数学学报，2009,23(3)。郭恒，张晓明，张晓明，基于随机k-SAT的快速抽样方法，中国科学院学报，2010。

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.