Reconstruction and Clustering in Random Constraint Satisfaction Problems

DOI10.1137/090755862zbMath1223.68077arXiv0904.2751MaRDI QIDQ3094944

Andrea Montanari, Ricardo L. Restrepo, Prasad Tetali

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

zbMATH Keywords

sharp threshold; message passing algorithms; random SAT

Mathematics Subject Classification ID

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

Charting the replica symmetric phase, The replica symmetric phase of random constraint satisfaction problems, Biased landscapes for random constraint satisfaction problems, On the Number of Solutions in Random Graphk-Colouring, Planting Colourings Silently, Unnamed Item, The condensation transition in random hypergraph 2-coloring, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Algorithmic obstructions in the random number partitioning problem, Reconstruction for the Potts model, Local convergence of random graph colorings, Gibbs measures and phase transitions on sparse random graphs, Phase transitions in discrete structures, Information-theoretic thresholds from the cavity method, Charting the replica symmetric phase, The number of solutions for random regular NAE-SAT, Sparse high-dimensional linear regression. Estimating squared error and a phase transition, Optimal testing for planted satisfiability problems, On the number of solutions in random hypergraph 2-colouring, The asymptotics of the clustering transition for random constraint satisfaction problems, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, The large deviations of the whitening process in random constraint satisfaction problems, On independent sets in random graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics