Random 3CNF formulas elude the Lovasz theta function

Uriel Feige, Eran Ofek

Let $\varphi$ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisf…