Biased landscapes for random constraint satisfaction problems

DOI10.1088/1742-5468/ab02deOpenAlexW2898951963MaRDI QIDQ5006920

Guilhem Semerjian, Louise Budzynski, Federico Ricci-Tersenghi

Publication date: 17 August 2021

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.01680

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Related Items (6)

Generic properties of a computational task predict human effort and performance ⋮ Random recursive hypergraphs ⋮ The asymptotics of the clustering transition for random constraint satisfaction problems ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Optimization of the dynamic transition in the continuous coloring problem

Uses Software

• ChainSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• A positive temperature phase transition in random hypergraph 2-coloring
• Reconstruction of random colourings
• Reconstruction on trees and spin glass transition
• Rigorous inequalities between length and time scales in glassy systems
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Information flow on trees
• The cavity method at zero temperature
• Reconstruction on trees: Beating the second eigenvalue
• Robust reconstruction on trees is determined by the second eigenvalue.
• On the dynamics of the glass transition on Bethe lattices
• On the freezing of variables in random constraint satisfaction problems
• Analyzing Walksat on Random Formulas
• Proof of the Satisfiability Conjecture for Large k
• Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Survey propagation as local equilibrium equations
• Diluted mean-field spin-glass models at criticality
• Erratum: Diluted mean-field spin-glass models at criticality
• Local entropy as a measure for sampling solutions in constraint satisfaction problems
• The large deviations of the whitening process in random constraint satisfaction problems
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• A new look at survey propagation and its generalizations
• Information, Physics, and Computation
• Factor graphs and the sum-product algorithm
• Analysing Survey Propagation Guided Decimation on Random Formulas
• Phase transitions in theq-coloring of random hypergraphs
• The Decimation Process in Random $k$-SAT
• Random Formulas Have Frozen Variables
• Walksat Stalls Well Below Satisfiability
• Survey propagation: An algorithm for satisfiability
• Gibbs states and the set of solutions of random constraint satisfaction problems
• A Better Algorithm for Random k-SAT
• Catching the k-NAESAT threshold
• The freezing threshold for k-colourings of a random graph
• Threshold values of random K‐SAT from the cavity method
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• Bicolouring random hypergraphs
• Frozen variables in random boolean constraint satisfaction problems
• The condensation transition in random hypergraph 2-coloring
• On the solution-space geometry of random constraint satisfaction problems
• Results related to threshold phenomena research in satisfiability: Lower bounds
• Lower bounds for random 3-SAT via differential equations
• Satisfiability threshold for random regular \textsc{nae-sat}

This page was built for publication: Biased landscapes for random constraint satisfaction problems