TIME: 1:30-2:20 pm,  November 7, 2006

PLACE: CSE 403

TITLE: Witnesses for non-satisfiability of dense random 3CNF formulas

SPEAKER: Uri Feige
         Microsoft Research and Weizmann Institute of Science
 

ABSTRACT:

We consider random 3CNF formulas with n variables and m clauses. It is
well known that when m > cn (for a sufficiently large constant c),
most formulas are not satisfiable. However, it is not known whether
such formulas are likely to have polynomial size witnesses that
certify that they are not satisfiable. We show that when m > cn^{7/5}
almost all 3CNF formulas have polynomial size witnesses for
nonsatisfiability.

Joint work with Jeong Han Kim and Eran Ofek