Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion

Abstract

We investigate the clustering transition undergone by an exemplary random constraint satisfaction problem, the bicoloring of $k$-uniform random hypergraphs, when its solutions are weighted non-uniformly, with a soft interaction between variables belonging to distinct hyperedges. We show that the threshold ${\alpha }_{\mathrm{d}}(k)$ for the transition can be further increased with respect to a restricted interaction within the hyperedges, and perform an asymptotic expansion of ${\alpha }_{\mathrm{d}}(k)$ in the large $k$ limit. We find that ${\alpha }_{\mathrm{d}}(k)=\frac{2^{k-1}}{k}(\ln k+\ln \ln k+{\gamma }_{\mathrm{d}}+o(1))$, where the constant ${\gamma }_{\mathrm{d}}$ is strictly larger than for the uniform measure over solutions.

arXiv comment33 pages, 11 figures, minor corrections

References in corpus (20)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• 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
• A better algorithm for random k-SAT
• Circumspect descent prevails in solving random constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Reconstruction of Random Colourings
• Typology of phase transitions in Bayesian inference problems
• Walksat stalls well below the satisfiability threshold
• Generating dense packings of hard spheres by soft interaction design
• Biased landscapes for random Constraint Satisfaction Problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Maximally flexible solutions of a random $K$-satisfiability formula

Cited by in corpus (4)

• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• 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
• Interacting Copies of Random Constraint Satisfaction Problems