__Israel CS THEORY DAY__

Open University of

Division of Computer Science

__Date__**: 17.3.08**

__Speaker__**: Uriel Feige**

__Title__**: How to refute random unsatisfiable
formulas.**

__Abstract__**:**

**Refuting unsatisfiable
3CNF formulas is one of the central co-NP-complete problems.
We consider the average case complexity of this problem, where the input
distributions are those of random and semi-random 3CNF formulas of high density
(clauses to variables ratio). The goal is to design efficient algorithms that
for almost every unsatisfiable input formula prove
that no satisfying assignment exists. We survey some results in this area, and
present some of the algorithmic techniques that are used.**