Survey-propagation decimation through distributed local computations

Abstract

We discuss the implementation of two distributed solvers of the random K-SAT problem, based on some development of the recently introduced survey-propagation (SP) algorithm. The first solver, called the "SP diffusion algorithm", diffuses as dynamical information the maximum bias over the system, so that variable nodes can decide to freeze in a self-organized way, each variable making its decision on the basis of purely local information. The second solver, called the "SP reinforcement algorithm", makes use of time-dependent external forcing messages on each variable, which let the variables get completely polarized in the direction of a solution at the end of a single convergence. Both methods allow us to find a solution of the random 3-SAT problem in a range of parameters comparable with the best previously described serialized solvers. The simulated time of convergence towards a solution (if these solvers were implemented on a distributed device) grows as log(N).

18 pages, 10 figures

References in corpus (5)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Lossy data compression with random gates
• Source coding by efficient selection of ground states clusters

Cited by in corpus (20)

• Phase Transitions in the Coloring of Random Graphs
• Learning by message-passing in networks of discrete synapses
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Locked constraint satisfaction problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Constraint satisfaction problems with isolated solutions are hard
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Sampling with flows, diffusion and autoregressive neural networks: A spin-glass perspective
• Message Passing for Optimization and Control of Power Grid: Model of Distribution System with Redundancy
• Encoding for the Blackwell Channel with Reinforced Belief Propagation
• Belief propagation for graph partitioning
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Statistical physics approach to graphical games: local and global interactions
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Coverage versus Supply Cost in Facility Location: Physics of Frustrated Spin Systems
• The network source location problem: ground state energy, entropy and effects of freezing
• Susceptibility Propagation for Constraint Satisfaction Problems
• The solution space structure of planted constraint satisfaction problems with growing domains
• Decimation flows in constraint satisfaction problems
• Minority Takeover in Majority Dynamics: Searching for Rare Initializations via the History Passing Algorithm