• Calendar

March 18, Tuesday
12:00 – 14:00

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 ofthe 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