Optimization of the dynamic transition in the continuous coloring problem

Abstract

Random constraint satisfaction problems can exhibit a phase where the number of constraints per variable $\alpha$ makes the system solvable in theory on the one hand, but also makes the search for a solution hard, meaning that common algorithms such as Monte-Carlo method fail to find a solution. The onset of this hardness is deeply linked to the appearance of a dynamical phase transition where the phase space of the problem breaks into an exponential number of clusters. The exact position of this dynamical phase transition is not universal with respect to the details of the Hamiltonian one chooses to represent a given problem. In this paper, we develop some theoretical tools in order to find a systematic way to build a Hamiltonian that maximizes the dynamic ${\alpha }_{\mathrm{d}}$ threshold. To illustrate our techniques, we will concentrate on the problem of continuous coloring, where one tries to set an angle $x_i\in [0;2\pi ]$ on each node of a network in such a way that no adjacent nodes are closer than some threshold angle $\theta$, that is $\cos (x_i-x_j)\le \cos \theta$. This problem can be both seen as a continuous version of the discrete graph coloring problem or as a one-dimensional version of the the Mari-Krzakala-Kurchan (MKK) model. The relevance of this model stems from the fact that continuous constraint satisfaction problems on sparse random graphs remain largely unexplored in statistical physics. We show that for sufficiently small angle $\theta$ this model presents a random first order transition and compute the dynamical, condensation and Kesten-Stigum transitions; we also compare the analytical predictions with Monte Carlo simulations for values of $\theta =2\pi /q$, $q\in \mathbb{N}$. Choosing such values of $q$ allows us to easily compare our results with the renowned problem of discrete coloring.

References in corpus (24)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Higher order glass-transition singularities in colloidal systems with attractive interactions
• Reentrant glass transition in a colloid-polymer mixture with depletion attractions
• Phase Transitions in the Coloring of Random Graphs
• Jamming versus Glass Transitions
• A Landscape Analysis of Constraint Satisfaction Problems
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• On the dynamics of the glass transition on Bethe lattices
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Robust reconstruction on trees is determined by the second eigenvalue
• Approximating the XY model on a random graph with a $q$-state clock model
• A thermodynamic description of colloidal glasses
• Biased landscapes for random Constraint Satisfaction Problems
• Generating dense packings of hard spheres by soft interaction design
• The large deviations of the whitening process in random constraint satisfaction problems
• Disorder-free spin glass transitions and jamming in exactly solvable mean-field models
• On the solution of a `solvable' model of an ideal glass of hard spheres displaying a jamming transition
• Maximally flexible solutions of a random $K$-satisfiability formula
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Postponing the dynamical transition density using competing interactions

Cited by in corpus (5)

• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression