Branching process approach for 2-sat thresholds

Elchanan Mossel, Arnab Sen

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


It is well known that, as n tends to∞, the probability of satisfiability for a random 2-SAT formula on n variables, where each clause occurs independently with probability α/2n, exhibits a sharp threshold at α = 1. We study a more general 2-SAT model in which each clause occurs independently but with probability αi/2n, where i ε {0, 1, 2} is the number of positive literals in that clause. We generalize the branching process arguments used byVerhoeven (1999) to determine the satisfiability threshold for this model in terms of the maximum eigenvalue of the branching matrix.

Original languageEnglish (US)
Pages (from-to)796-810
Number of pages15
JournalJournal of Applied Probability
Issue number3
StatePublished - Sep 2010


  • 2-SAT
  • Phase transition
  • Satisfiability
  • Two-type branching process


Dive into the research topics of 'Branching process approach for 2-sat thresholds'. Together they form a unique fingerprint.

Cite this