Danny Vilenchik
Tel Aviv University
April 9, 2008
Title: On satisfiable k-CNF formulas above the threshold
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, 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