Random subcubes as a toy model for constraint satisfaction problems

DOI10.1007/s10955-008-9543-xzbMath1214.82045arXiv0710.3804MaRDI QIDQ937116

Thierry Mora, Lenka Zdeborová

Publication date: 20 August 2008

Published in: Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0710.3804

zbMATH Keywords

constraint satisfaction problems; exactly solvable models; clustering of solutions

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

90C27: Combinatorial optimization

82D30: Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses)

82B23: Exactly solvable models; Bethe ansatz

82B41: Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics

05C15: Coloring of graphs and hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Rigorous inequalities between length and time scales in glassy systems
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
• The 3-XORSAT threshold.
• Rigorous low-temperature results for the mean field \(p\)-spins interaction model
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• On the dynamics of the glass transition on Bethe lattices
• On the freezing of variables in random constraint satisfaction problems
• Replica symmetry breaking and the nature of the spin glass phase
• Quiet Planting in the Locked Constraint Satisfaction Problems
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Factor graphs and the sum-product algorithm
• Random codes: minimum distances and error exponents
• Gibbs states and the set of solutions of random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems