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.