Biased landscapes for random Constraint Satisfaction Problems

Abstract

The typical complexity of Constraint Satisfaction Problems (CSPs) can be investigated by means of random ensembles of instances. The latter exhibit many threshold phenomena besides their satisfiability phase transition, in particular a clustering or dynamic phase transition (related to the tree reconstruction problem) at which their typical solutions shatter into disconnected components. In this paper we study the evolution of this phenomenon under a bias that breaks the uniformity among solutions of one CSP instance, concentrating on the bicoloring of k-uniform random hypergraphs. We show that for small k the clustering transition can be delayed in this way to higher density of constraints, and that this strategy has a positive impact on the performances of Simulated Annealing algorithms. We characterize the modest gain that can be expected in the large k limit from the simple implementation of the biasing idea studied here. This paper contains also a contribution of a more methodological nature, made of a review and extension of the methods to determine numerically the discontinuous dynamic transition threshold.

arXiv comment32 pages, 16 figures

References in corpus (39)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• Phase Transitions in the Coloring of Random Graphs
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Reconstruction on trees and spin glass transition
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Survey Propagation as local equilibrium equations
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• On the freezing of variables in random constraint satisfaction problems
• On the dynamics of the glass transition on Bethe lattices
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• A better algorithm for random k-SAT
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Robust reconstruction on trees is determined by the second eigenvalue
• Reconstruction of Random Colourings
• Catching the k-NAESAT Threshold
• Typology of phase transitions in Bayesian inference problems
• The condensation transition in random hypergraph 2-coloring
• Diluted Mean-Field Spin-Glass Models at Criticality
• Walksat stalls well below the satisfiability threshold
• Generating dense packings of hard spheres by soft interaction design
• Phase transitions in the $q$-coloring of random hypergraphs
• Bicoloring Random Hypergraphs
• A positive temperature phase transition in random hypergraph 2-coloring
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Analyzing Walksat on random formulas
• The decimation process in random k-SAT
• Reconstruction of colourings without freezing

Cited by in corpus (15)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Learning from Survey Propagation: a Neural Network for MAX-E-$3$-SAT
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• A theory of non-equilibrium local search on random satisfaction problems
• Random Recursive Hypergraphs
• Maximally flexible solutions of a random $K$-satisfiability formula
• Gardner formula for Ising perceptron models at small densities
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Optimization of the dynamic transition in the continuous coloring problem
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Interacting Copies of Random Constraint Satisfaction Problems