Bounds for random constraint satisfaction problems via spatial coupling

DOI10.1137/1.9781611974331.CH35MaRDI QIDQ4575612zbMATH OpenOpenAlexFDO

Authors

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1765f446ada8e2733ac109a546f7ce290c774322

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Threshold saturation in spatially coupled constraint satisfaction problems
• Reconstruction and clustering in random constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• Catching the \(k\)-NAESAT threshold
• On the solution-space geometry of random constraint satisfaction problems

Cited in

(5)

• Charting the replica symmetric phase
• Threshold saturation in spatially coupled constraint satisfaction problems
• Spin systems on Bethe lattices
• Unsatisfiability bounds for random CSPs from an energetic interpolation method
• Spines of random constraint satisfaction problems: definition and connection with computational complexity

This page was built for publication: Bounds for random constraint satisfaction problems via spatial coupling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575612)