BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T091507Z
UID:Seminar-dept-1042@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20230509T130000
DTEND:20230509T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Andreas Galanis: Fast sampling of satisfying assignments from the k-SAT model \n\nRandom constraint satisfaction problems, such as the k-SAT model, have long posed various algorithmic and probabilistic challenges. In this talk, we focus on understanding algorithmically the solution space of k-SAT formulas, and consider the problem of sampling a satisfying assignment from the k-SAT model (i.e., a k-SAT formula chosen uniformly at random among those with m clauses and n variables). \n\n\n\nThe best previously known algorithm for the k-SAT model applied when the density of the formula m/n is less than 2^(k/300) and had a large running time of n^(exp(Θ(k)). We design a significantly faster algorithm based on a Markov chain, which runs in nearly-linear time and works up to densities 2^(k/26).  \n\n\n\nThe main challenge for the k-SAT model is the presence of many variables with unbounded degree which causes significant correlations within the formula and impedes the application of relevant Markov chain methods from the bounded-degree setting. Instead, we use the spectral-independence framework of [Anari, Liu and Oveis-Gharan, FOCS'20] which has recently yielded various breakthroughs in Markov-chain analysis. Our main contribution is to develop the framework for k-SAT formulas in a way that is robust against the presence of high-degree variables.\n\n\n\nBased on work with Z. Chen, L. A. Goldberg, H. Guo, A. Herrera-Poyatos, N. Mani, and A. Moitra.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1042
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR