Algorithms for Random k-SAT and Colouring Random Graphs
|Affiliation:||University of Toronto|
|Room:||Mathematics 3 (M3) 3103|
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.
200 University Avenue West
Waterloo, ON N2L 3G1