Reconstruction and Clustering in Random Constraint Satisfaction Problems
From MaRDI portal
Publication:3094944
DOI10.1137/090755862zbMath1223.68077arXiv0904.2751MaRDI QIDQ3094944
Prasad Tetali, Ricardo L. Restrepo, Andrea Montanari
Publication date: 27 October 2011
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0904.2751
05C80: Random graphs (graph-theoretic aspects)
82B26: Phase transitions (general) in equilibrium statistical mechanics
05C15: Coloring of graphs and hypergraphs
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Related Items
Planting Colourings Silently, Reconstruction for the Potts model, Local convergence of random graph colorings, Gibbs measures and phase transitions on sparse random graphs, Information-theoretic thresholds from the cavity method, Charting the replica symmetric phase, Optimal testing for planted satisfiability problems, On the number of solutions in random hypergraph 2-colouring, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, On independent sets in random graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics