Branching Process Approach for 2-Sat Thresholds

DOI10.1239/jap/1285335410zbMath1214.68180arXiv0803.3285OpenAlexW2044574028MaRDI QIDQ4933200

Elchanan Mossel, Arnab Sen

Publication date: 12 October 2010

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionsatisfiability2-SATtwo-type branching process

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• On the hardness of sampling independent sets beyond the tree threshold
• Correlation inequalities on some partially ordered sets
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Random 2-SAT and unsatisfiability
• On the satisfiability threshold of formulas with three literals per clause
• Limit theorems for decomposable multi-dimensional Galton-Watson processes
• Random 2-SAT with prescribed literal degrees
• The scaling window of the 2-SAT transition
• The ?(2) limit in the random assignment problem
• Counting independent sets up to the tree threshold
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• A new look at survey propagation and its generalizations
• Sharp thresholds for constraint satisfaction problems and homomorphisms
• The Forwarding Indices of Random Graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Threshold values of random K‐SAT from the cavity method
• The probabilistic analysis of a greedy satisfiability algorithm
• The complexity of theorem-proving procedures
• On the solution-space geometry of random constraint satisfaction problems