BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Random k-sat. A review and some new results. Markström, Klas


In this talk I will both give a review of the behaviour of random k-sat formulae and present some new variations on the problem. In the study of random K-sat one constructs a k-sat formula with n variables and m clauses at random. When m is small the formula is most often satisfiable and when m i large it is most likely unsatisfiable. We also know that there is a sharp transition between these to cases, often referred to as a phase transition. Empirically is has been observed that sat-solvers have a peak in their typically running time when m is close to this phase transition, and a longer number of conjectures has been made about this behaviour.

I will review what is now known from mathematical results and also discuss how well, or badly, some of the old conjectures and observations have held up against both mathematics and recent, far more extensive, experiments. I will also mention some recent work on unbalanced versions of k-sat which display interesting behaviours.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International