Reconstruction and Clustering in Random Constraint Satisfaction Problems
From MaRDI portal
Publication:3094944
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
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