Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
arXiv:2406.01710 · doi:10.1088/1751-8121/ad8797
Abstract
We study the fixed points of outer-totalistic cellular automata on sparse random regular graphs. These can be seen as constraint satisfaction problems, where each variable must adhere to the same local constraint, which depends solely on its state and the total number of its neighbors in each possible state. Examples of this setting include classical problems such as independent sets or assortative/dissasortative partitions. We analyse the existence and number of fixed points in the large system limit using the cavity method, under both the replica symmetric (RS) and one-step replica symmetry breaking (1RSB) assumption. This method allows us to characterize the structure of the space of solutions, in particular, if the solutions are clustered and whether the clusters contain frozen variables. This last property is conjectured to be linked to the typical algorithmic hardness of the problem. We bring experimental evidence for this claim by studying the performance of the belief-propagation reinforcement algorithm, a message-passing-based solver for these constraint satisfaction problems.
arXiv comment26 pages, 7 figures
References in corpus (30)
- The Bethe lattice spin glass revisited
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Statistical physics of inference: Thresholds and algorithms
- Phase Transitions in the Coloring of Random Graphs
- Recipes for metastable states in Spin Glasses
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Lattice Glass Models
- Reconstruction on trees and spin glass transition
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Glass models on Bethe lattices
- A variational description of the ground state structure in random satisfiability problems
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
- The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Landscape of solutions in constraint satisfaction problems
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Origin of the computational hardness for learning with binary synapses
- Survey-propagation decimation through distributed local computations
- Constraint satisfaction problems with isolated solutions are hard
- Outer-totalistic cellular automata on graphs
- Statistical Mechanics of the Minimum Dominating Set Problem
- Geometrical organization of solutions to random linear Boolean equations
- Disordered Systems Insights on Computational Hardness
- Statistical Mechanics of maximal independent sets
- The hard-core model on random graphs revisited
- Statistical Physics of Hard Optimization Problems
- Phase transitions in the -coloring of random hypergraphs
- Dynamical Phase Transitions in Graph Cellular Automata
- Backtracking Dynamical Cavity Method