On the maximum satisfiability of random formulas

Dimitris Achlioptas, Assaf Naor, Yuval Peres

Research output: Contribution to journalArticlepeer-review


Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 - 2-k +p 2-k of its clauses (note that every k-CNF formula is 0-satisfiable). Let Fk(n, m) denote a random k-CNF formula on n variables with m clauses. For every k2 and every r>0 we determine p and Δ=Δ(k)=O(k2-k/2) such that with probability tending to 1 as n→, a random k-CNF formula F k(n, rn) is p-satisfiable but not (p+Δ)-satisfiable.

Original languageEnglish (US)
Article number1219098
JournalJournal of the ACM
Issue number2
StatePublished - Apr 1 2007


  • Maximum satisfiability

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'On the maximum satisfiability of random formulas'. Together they form a unique fingerprint.

Cite this