Dynamical cavity method for hypergraphs and its application to quenches in the problem
- 9 July 2025
- journal article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 112 (1) , 014306
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 work extends these methods to hypergraphs, enabling the analysis of interactions involving more than two variables. We apply them to analyze the k-XOR-satisfiability 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.Keywords
Funding Information
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (205602)
This publication has 36 references indexed in Scilit:
- The Satisfiability Threshold fork-XORSATCombinatorics, Probability and Computing, 2015
- Hypergraph Theory2013
- Transversals of subtree hypergraphs and the source location problem in digraphsNetworks, 2007
- Gibbs states and the set of solutions of random constraint satisfaction problemsProceedings of the National Academy of Sciences, 2007
- Two Solutions to Diluted p-Spin Models and XORSAT ProblemsJournal of Statistical Physics, 2003
- The Cavity Method at Zero TemperatureJournal of Statistical Physics, 2003
- The Bethe lattice spin glass revisitedThe European Physical Journal B, 2001
- A hypergraph model for constraint logic programming and applications to bus drivers' schedulingAnnals of Mathematics and Artificial Intelligence, 1993
- Decreasing energy functions as a tool for studying threshold networksDiscrete Applied Mathematics, 1985
- Spin glasses with p-spin interactionsNuclear Physics B, 1985