Back to ARC Colloquium page

**Two talks will be given by Dr. Vilenchick - please read to bottom of page

February 18, 2008
Danny Vilenchik
School of Computer Science, Tel Aviv University

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, 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.

Title: On the tractability of coloring semirandom graphs

As part of the efforts put in understanding the intricacies of the k-colorability problem different distributions over k-colorable graphs were analyzed. While the problem is
notoriously hard (not even reasonably approximable) in the worst case, the average case (with respect to such distributions) often turns out to be "easy''.
Semi-random models mediate between these two extremes and may be more suitable to imitate "real-life'' instances than purely random models. In this talk we shall consider semi-random variants of the planted k-colorability distribution. Our aim is to study a general semi-random framework for k-colorable graphs with constant average degree, thus hopefully gaining some further understanding as to what makes this problem so hard and which algorithmic tools may be of interest in this context.
 
Based on joint work with Michael Krivelevich and Julia Boettcher.