Tutte seminar - Mike Molloy

Algorithms for Random k-SAT and Colouring Random Graphs

Abstract:

Random instances of k-SAT have long been recognized as being very challenging to solve algorithmically. Random graphs are also very difficult to colour. A series of hypotheses arising from statistical physics provides much insight into why these problems are so challenging. These hypotheses also give rise to some algorithms which, in practice, perform remarkably well on random instances of k-SAT and on k-colouring random graphs for small values of k. The most notable such algorithm is survey propagation, a variation of belief propagation.

This talk will provide an overview of these algorithms, including intuition as to why they seem to perform well and hypotheses regarding their performance for large values of k. We will also discuss what has been proven and what we hope to prove.