Local equations describe unreasonably efficient stochastic algorithms in random K-SAT

Area of Science:

• Theoretical Computer Science
• Statistical Physics
• Combinatorial Optimization

Background:

• The performance of algorithms solving complex constraint satisfaction problems is not fully understood due to a lack of tools for analyzing their dynamics.
• Understanding the out-of-equilibrium dynamics of local search algorithms is crucial for improving combinatorial optimization.

Purpose of the Study:

• To develop a theoretical framework for analyzing the dynamics of local search algorithms in constraint satisfaction problems.
• To provide insights into the performance of algorithms like Focused Metropolis Search (FMS) and greedy-WalkSAT (G-WalkSAT).

Main Methods:

• Development of a system of approximate master equations to model local search algorithm behavior.
• Comparison of the framework's predictions with phase diagrams of FMS and G-WalkSAT on random 3-SAT.
• Application of the equations in a decimation scheme to analyze solution space structure.

Main Results:

• The approximate master equations show good qualitative agreement with algorithm phase diagrams.
• The framework confirms G-WalkSAT's parameter-independent threshold and predicts FMS's threshold beyond the clustering transition.
• The decimation approach yields a threshold surpassing conventional methods, outperforming Belief Propagation-guided decimation.

Conclusions:

• The developed framework provides a novel theoretical tool for analyzing local search dynamics in constraint satisfaction problems.
• The results challenge assumptions about the necessity of long-range correlations for efficient local search.
• This work opens new avenues for designing more efficient algorithms for combinatorial optimization tasks.