Gibbs states and the set of solutions of random constraint satisfaction problems

DOI10.1073/pnas.0703685104zbMath1190.68031OpenAlexW2168290833WikidataQ35973227 ScholiaQ35973227MaRDI QIDQ5385913

Florent Krzakala, Federico Ricci-Tersenghi, Lenka Zdeborová, Guilhem Semerjian, Andrea Montanari

Publication date: 7 May 2008

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1073/pnas.0703685104

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Queueing theory (aspects of probability theory) (60K25) Classical equilibrium statistical mechanics (general) (82B05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

On the solution‐space geometry of random constraint satisfaction problems, The number of satisfying assignments of random 2‐SAT formulas, Combinatorial statistics and the sciences, One-step replica symmetry breaking of random regular NAE-SAT. II, Optimization algorithms for multi-species spherical spin glasses, On the structure of the set of panchromatic colorings of a random hypergraph, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Shattering versus metastability in spin glasses, On a Connectivity Threshold for Colorings of Random Graphs and Hypergraphs, Satisfiability threshold for power law random 2-SAT in configuration model, Satisfiability threshold for random regular \textsc{nae-sat}, The condensation phase transition in random graph coloring, Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Generalized approximate survey propagation for high-dimensional estimation ^*, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Generic properties of a computational task predict human effort and performance, Phase transitions in discrete structures, On the Complexity of Random Satisfiability Problems with Planted Solutions, On the sufficiency of pairwise interactions in maximum entropy models of networks, A positive temperature phase transition in random hypergraph 2-coloring, Reconstruction of random colourings, On independent sets in random graphs, Satisfiability transition in asymmetric neural networks, Completeness, approximability and exponential time results for counting problems with easy decision version, Mean field theory of jamming of nonspherical particles, Random \(\mathbb{Z}^d\)-shifts of finite type, The solution space structure of planted constraint satisfaction problems with growing domains, Random Instances of Problems in NP – Algorithms and Statistical Physics, Information-theoretic thresholds from the cavity method, Strong replica symmetry in high-dimensional optimal Bayesian inference, Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP, On the concentration of the number of solutions of random satisfiability formulas, On the number of solutions in random hypergraph 2-colouring, The asymptotics of the clustering transition for random constraint satisfaction problems, Limits of discrete distributions and Gibbs measures on random graphs, Proof of the satisfiability conjecture for large \(k\), Maximum independent sets on random regular graphs, The algorithmic hardness threshold for continuous random energy models, On the thresholds in linear and nonlinear Boolean equations, Statistical mechanics of the minimum dominating set problem, Upper-bounding the \(k\)-colorability threshold by counting covers, Harnessing the Bethe free energy, On the chromatic number of random regular graphs, Exact thresholds for Ising-Gibbs samplers on general graphs, The asymptotic \(k\)-SAT threshold, Phase transitions in theq-coloring of random hypergraphs, Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem, Planting Colourings Silently, Threshold saturation in spatially coupled constraint satisfaction problems, Out-of-equilibrium dynamical mean-field equations for the perceptron model, Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results, On the connectivity of proper colorings of random graphs and hypergraphs, Bipartitioning of directed and mixed random graphs, The replica symmetric solution for Potts models on \(d\)-regular graphs, Dreaming neural networks: rigorous results, Random-link matching problems on random regular graphs, Dismantlability, connectedness, and mixing in relational structures, Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One, Bethe states of random factor graphs, Random subcubes as a toy model for constraint satisfaction problems, The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Next nearest neighbour Ising models on random graphs, Statistical mechanics of complex neural systems and high dimensional data, Low-temperature excitations within the Bethe approximation, Boolean constraint satisfaction problems for reaction networks, Organization mechanism and counting algorithm on vertex-cover solutions, Local entropy as a measure for sampling solutions in constraint satisfaction problems, The large deviations of the whitening process in random constraint satisfaction problems, Circular coloring of random graphs: statistical physics investigation, Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics, Constructing concrete hard instances of the maximum independent set problem, A Spectral Approach to Analysing Belief Propagation for 3-Colouring, The Decimation Process in Random k-SAT, Charting the replica symmetric phase, Charting the replica symmetric phase, On the freezing of variables in random constraint satisfaction problems, Constraining the clustering transition for colorings of sparse random graphs, A model with Darwinian dynamics on a rugged landscape, The satisfiability threshold for random linear equations, Physics and complexity, Ising models on locally tree-like graphs, Optimal testing for planted satisfiability problems, Spin systems on Bethe lattices, Gibbs measures and phase transitions on sparse random graphs, Reconstruction for the Potts model, Local convergence of random graph colorings, CRITICALITY AND HETEROGENEITY IN THE SOLUTION SPACE OF RANDOM CONSTRAINT SATISFACTION PROBLEMS, On the Potts antiferromagnet on random graphs, A rigorous analysis of the cavity equations for the minimum spanning tree, The set of solutions of random XORSAT formulae, On the Number of Solutions in Random Graphk-Colouring, Statistical and algebraic analysis of a family of random Boolean equations, Dismantlability, Connectedness, and Mixing in Relational Structures, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Optimization of mean-field spin glasses, The condensation transition in random hypergraph 2-coloring, The number of solutions for random regular NAE-SAT, Localization in the discrete non-linear Schrödinger equation and geometric properties of the microcanonical surface, A simple one dimensional glassy Kac model, The Cut Metric for Probability Distributions, The replica symmetric phase of random constraint satisfaction problems, Deterministic counting of graph colourings using sequences of subgraphs, Geometric properties of satisfying assignments of random ε-1-in-kSAT, Belief propagation on the random \(k\)-SAT model, Comparing dynamics: deep neural networks versus glassy systems, Biased landscapes for random constraint satisfaction problems, Unnamed Item, Unnamed Item, Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio, Poisson-Dirichlet asymptotics in condensing particle systems, Optimization of the dynamic transition in the continuous coloring problem, Minimal contagious sets in random regular graphs, Walksat Stalls Well Below Satisfiability, Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length, Decoding from Pooled Data: Sharp Information-Theoretic Bounds

Cites Work

• Reconstruction on trees and spin glass transition
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Information flow on trees
• Uniqueness of uniform random colorings of regular trees
• A mathematical reformulation of Derrida's REM and GREM
• Coloring Random Graphs
• Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• Factor graphs and the sum-product algorithm
• On the p-spin interaction model at low temperature
• Threshold values of random K‐SAT from the cavity method
• Additional Limit Theorems for Indecomposable Multidimensional Galton-Watson Processes
• The chromatic number of random graphs