On the complexity of 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 determines
when 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.