On the complexity of approximating partition functions

关于近似配分函数的复杂性

• 批准号: 2763180
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2019
• 资助国家: 英国
• 起止时间: 2019 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2763180
• 关键词: complexity; approximating; partition; functions

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.

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