Combinatorics Seminar
When: Sunday, May 25, 10am
Where: Schreiber 309
Speaker: Dan Vilenchik, Tel Aviv University,
Title: An average case study of some satisfiability problems
(PhD defence talk)
Abstract:
Constraint satisfaction problems play an important role in many
areas of computer science, e.g. computational complexity
theory, coding theory, and artificial
intelligence, to mention just a few. The main challenge is to devise
efficient algorithms for finding satisfying
assignments (when such exist), or conversely to provide a certificate
of unsatisfiability. One of the best known examples of a
constraint satisfaction problem is k-SAT, which is the first to be
proven as NP-complete.
k-CNF formulas with m clauses over n variables show a phase
transition phenomenon in the following aspect. There
exists d=d(k,n) such that almost all formulas with m/n>d are not
satisfiable whereas most formulas with m/n below d
are. While random k-CNFs below the threshold received much attention
in recent years, above-threshold distributions over satisfiable
k-CNFs were far less studied. One possible reason is that it is not
clear how to define such distributions in a natural way,
while keeping the problem approachable in some sense.
Our main contribution is a rigorous average-case study
of above-threshold satisfiable k-CNF formulas.
More specifically, we shall concentrate on three distributions: the
planted k-SAT distribution, the uniform distribution over satisfiable
k-CNF formulas (in the regime m/n>d(k,n)), and an "on-line" version
of the uniform distribution.
Solving a long-standing open question, we are able to show that
unlike the typically complicated structure of the solution space of
below-threshold formulas, above threshold formulas (in all three
distributions) have a simple, basically single-solution structure. We
also present some algorithmic ideas that are useful for solving
certain clause-density regimes of these distributions.
Based on joint works with: Amin Coja-Oghlan, Uriel Feige, Abraham
Flaxman, Michael Krivelevich, and Benjamin Sudakov.