Unsatisfiability bounds for random CSPs from an energetic interpolation method

DOI10.1007/978-3-642-31594-7_1MaRDI QIDQ2843226zbMATH OpenOpenAlexFDO

Authors Ricardo Menchaca-Mendez, D. Achlioptas

Publication date 12 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31594-7_1

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Bounds for random constraint satisfaction problems via spatial coupling
• Proof of the satisfiability conjecture for large \(k\)
• Going after the k-SAT threshold
• Random constraint satisfaction: A more accurate picture
• Reconstruction and clustering in random constraint satisfaction problems

Cited in

(1)

• Unimodality, independence lead to NP-hardness of interval probability problems

This page was built for publication: Unsatisfiability bounds for random CSPs from an energetic interpolation method

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