Random subcubes as a toy model for constraint satisfaction problems

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

Lenka Zdeborová, Thierry Mora

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 problemsexactly solvable modelsclustering of solutions

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial optimization (90C27) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Exactly solvable models; Bethe ansatz (82B23) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Coloring of graphs and hypergraphs (05C15)

Related Items

Revisiting the replica trick: competition between spin glass and conventional order ⋮ The condensation transition in random hypergraph 2-coloring

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

This page was built for publication: Random subcubes as a toy model for constraint satisfaction problems