The poisson cloning model for random k-SAT Seminars/Workshops

Abstract

We will introduce a new model for random k-SAT problems, called the Poisson cloning model, in which all degrees are i.i.d. Poisson random variables. After showing how close this model is to the usual random k-SAT model, we will prove threshold phenomena of the pure literal algorithms. Other algorithms like the unit clause algorithms will be also discussed. This, in particular, reproves an earlier result of Bollobas, Borgs, Chayes, Kim and Wilson about the scaling window of random 2-SAT.