Amin Coja-Oghlan

We study the Lovasz number theta along with two further SDP relaxations $\thetI$, $\thetII$

of the independence number and the corresponding relaxations of the

chromatic number on random graphs G(n,p). We prove that \theta is

concentrated about its mean, and that the relaxations of the chromatic

number in the case ...
more >>>

Eran Ofek, Uriel Feige

Let $\phi$ 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

satisfiable. It is an open question whether there is an efficient

refutation algorithm that for most such formulas proves ...
more >>>