Reconstruction and Clustering in Random Constraint Satisfaction Problems
From MaRDI portal
Publication:3094944
DOI10.1137/090755862zbMath1223.68077arXiv0904.2751OpenAlexW1818081266MaRDI 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
Random graphs (graph-theoretic aspects) (05C80) Phase transitions (general) in equilibrium statistical mechanics (82B26) Coloring of graphs and hypergraphs (05C15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Phase transitions in discrete structures, Sparse high-dimensional linear regression. Estimating squared error and a phase transition, On independent sets in random graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics, Information-theoretic thresholds from the cavity method, On the number of solutions in random hypergraph 2-colouring, The asymptotics of the clustering transition for random constraint satisfaction problems, Combinatorial statistics and the sciences, Algorithmic obstructions in the random number partitioning problem, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Planting Colourings Silently, The large deviations of the whitening process in random constraint satisfaction problems, Charting the replica symmetric phase, Charting the replica symmetric phase, Optimal testing for planted satisfiability problems, Gibbs measures and phase transitions on sparse random graphs, Reconstruction for the Potts model, Local convergence of random graph colorings, On the Number of Solutions in Random Graphk-Colouring, The condensation transition in random hypergraph 2-coloring, The number of solutions for random regular NAE-SAT, The replica symmetric phase of random constraint satisfaction problems, Biased landscapes for random constraint satisfaction problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Unnamed Item
