The asymptotics of the clustering transition for random constraint satisfaction problems
DOI10.1007/s10955-020-02635-8zbMath1505.68030arXiv1911.09377OpenAlexW3093852371MaRDI QIDQ2659305
Louise Budzynski, Guilhem Semerjian
Publication date: 26 March 2021
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.09377
spin glassesdisordered systemsstatistical physicsconstraint satisfaction problemstree reconstruction
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Phase transitions (general) in equilibrium statistical mechanics (82B26) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstruction of random colourings
- Reconstruction on trees and spin glass transition
- Rigorous inequalities between length and time scales in glassy systems
- Ratio of the tail of an infinitely divisible distribution on the line to that of its Lévy measure
- Information flow on trees
- On the freezing of variables in random constraint satisfaction problems
- Approximations of small jumps of Lévy processes with a view towards simulation
- Nonnormal Small Jump Approximation of Infinitely Divisible Distributions
- Proof of the Satisfiability Conjecture for Large k
- Reconstruction and Clustering in Random Constraint Satisfaction Problems
- Modern Coding Theory
- Reconstruction Threshold for the Hardcore Model
- Factor graphs and the sum-product algorithm
- Phase transitions in theq-coloring of random hypergraphs
- A second threshold for the hard‐core model on a Bethe lattice
- Statistical Physics of Spin Glasses and Information Processing
- Biased landscapes for random constraint satisfaction problems
- Survey propagation: An algorithm for satisfiability
- Gibbs states and the set of solutions of random constraint satisfaction problems
- The freezing threshold for k-colourings of a random graph
- Threshold values of random K‐SAT from the cavity method
- On the solution-space geometry of random constraint satisfaction problems
This page was built for publication: The asymptotics of the clustering transition for random constraint satisfaction problems
