Friday November 16th, 2007
3:30pm
WEH 7220
Satisfiable k-CNF Distributions above the Threshold
Danny Vilenchik
Tel-Aviv University
Abstract: 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 < 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.
In this talk we will survey recent developments in this area. 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.
In all cases we are able to show that unlike the typically complicated structure of the solution space of below-threshold formulas, the above threshold formulas 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.
