Tutte seminar - Mike MolloyExport this event to calendar

Friday, June 13, 2014 — 3:30 PM EDT

Algorithms for Random k-SAT and Colouring Random Graphs

Speaker: Mike Molloy
Affiliation: University of Toronto
Room: Mathematics 3 (M3) 3103

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.

Location 
M3 - Mathematics 3
3103
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
  1. 2021 (90)
    1. October (2)
    2. September (12)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)