Dynamical Cavity Method for Hypergraphs and its Application to Quenches in the k-XOR-SAT Problem

Abstract

The dynamical cavity method and its backtracking version provide a powerful approach to studying the properties of dynamical processes on large random graphs. This paper extends these methods to hypergraphs, enabling the analysis of interactions involving more than two variables. We apply them to analyse the $k$-XOR-satisfiability ($k$-XOR-SAT) problem, an important model in theoretical computer science which is closely related to the diluted $p$-spin model from statistical physics. In particular, we examine whether the quench dynamics -- a deterministic, locally greedy process -- can find solutions with only a few violated constraints on $d$-regular $k$-uniform hypergraphs. Our results demonstrate that the methods accurately characterize the attractors of the dynamics. It enables us to compute the energy reached by typical trajectories of the dynamical process in different parameter regimes. We show that these predictions are accurate, including cases where a classical mean-field approach fails.

26 pages

References in corpus (22)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• A ferromagnet with a glass transition
• Simplest random K-satisfiability problem
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Dynamic message-passing equations for models with unidirectional dynamics
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Majority dynamics on trees and the dynamic cavity method
• The Cavity Approach to Parallel Dynamics of Ising Spins on a Graph
• Dissipative phase transitions in the fully-connected Ising model with $p$-spin interaction
• Conjecture on the maximum cut and bisection width in random regular graphs
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• Statistical mechanics of coupled supercooled liquids in finite dimensions
• On the number of limit cycles in asymmetric neural networks
• The set of solutions of random XORSAT formulae
• Dynamical Phase Transitions in Graph Cellular Automata
• Backtracking Dynamical Cavity Method
• Improved mean-field dynamical equations are able to detect the two-steps relaxation in glassy dynamics at low temperatures
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs