Dynamical cavity method for hypergraphs and its application to quenches in the k-XOR-SAT problem

Area of Science:

• Statistical physics and theoretical computer science
• Complex systems and network analysis
• Random graph theory and hypergraph dynamics

Background:

• Dynamical cavity methods are effective for analyzing random graph processes.
• Extending these methods to hypergraphs allows for studying multi-variable interactions.
• The k-XOR-satisfiability problem is a key model in theoretical computer science.

Purpose of the Study:

• To extend dynamical cavity methods and their backtracking versions to hypergraphs.
• To analyze the k-XOR-satisfiability problem on d-regular k-uniform hypergraphs.
• To investigate the effectiveness of quench dynamics in finding near-solutions.

Main Methods:

• Application of extended dynamical cavity methods to hypergraphs.
• Analysis of quench dynamics, a deterministic, locally greedy process.
• Computation of energy levels reached by dynamical trajectories.

Main Results:

• The extended methods accurately characterize the attractors of the dynamics on hypergraphs.
• Accurate computation of energy levels for typical dynamical trajectories across parameter regimes.
• Demonstrated accuracy of predictions, outperforming classical mean-field approaches.

Conclusions:

• Dynamical cavity methods are successfully extended to hypergraphs, offering a powerful analytical tool.
• The study validates the accuracy of these methods for complex problems like k-XOR-satisfiability.
• These advancements provide new insights into the behavior of dynamical processes on complex networks.