Partition function estimation and phase transitions on random satisfiability problems
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
This thesis emphasizes on the estimation of partition functions and analyse phase transitions in random satisfiability problems with focuses on random 2-SAT, random k-XORSAT and random k-SAT models. Partition functions capture the exponential growth of solution spaces and establish a bridge among com-
binatorics, probability, and statistical physics. Studying their asymptotic and fluctuations helps us to understand the mechanisms behind sharp phase transitions and the solution space geometry in random constraint satisfaction problems.
Our first contribution establishes a central limit theorem for the number of solutions (also called ‘partition function’ in physics jargon) of random 2-SAT – first CLT of this type for any random CSPs. Thereby it provides a precise probabilistic characterization of fluctuations on the logarithm of the number of satisfying assignments of order √n with n the number of variables. In addition to this we effectively evaluated the formula for variance on the number of random 2-SAT solutions. The proof techniques rely on the Martingale central limit theorem along with the Gibbs uniqueness property and the local convergence to the Galton-Watson tree combined with a coupling argument called ‘Aizenmann-Sims-Starr scheme’.
The second part of the thesis investigates the performance of a statistical physics inspired message passing algorithm called ‘Belief Propagation Guided Decimation’ on the random k-XORSAT problem. Specifically, we derive an explicit threshold upto which the algorithm succeeds with a strictly positive probability between 0 and 1. Additionally, we study a thought experiment called ‘Decimation process’ for which we determine different phase transitions such as (non)-reconstruction and condensation phase transition and their connection to BPGD (in which regimes these two processes diverge or converge).
Finally, for random k-SAT, we revisited the Gibbs uniqueness threshold, improving the lower bound over the previous work by Montanari and Shah in 2007. More specifically, we count the number of actual satisfying assignments of random k-SAT which is given by the physics inspired ‘replica symmetry solution’ upto the Gibbs uniqueness threshold. Mathematically, we find an explicit expression on the logarithm of the number of solutions of random k-SAT in terms of the Bethe free entropy which is a function defined for a probability measure in the unit interval. Moreover, our lower bound in contrast to Montanari-Shah bound is significant particularly for small k.
In a nutshell, this thesis advances the rigorous understanding of random satisfiability problems by combining the algorithmic analysis, probabilistic combinatorics and statistical physics equipment. In light of both the structural properties of random formulas and the effectiveness of different message passing algorithms along with the universal principles governing fluctuations, correlation decay and mathematical foundation for the phenomena predicted by spin glass theory, point toward new directions for the future research on random satisfiability problems.
Description
Table of contents
Keywords
Random graph, Probabilistic combinatorics, Satisfiability threshold
Subjects based on RSWK
Zufallsgraph, Kombinatorik, Erfüllbarkeitsproblem