Department seminar by Pascal MaillardExport this event to calendar

Wednesday, October 20, 2021 — 11:00 AM EDT

Please Note: This seminar will be given online.

Probability seminar series

Pascal Maillard
Université Toulouse III - Paul Sabatier

Link to join seminar: Hosted on Zoom

Understanding algorithmic hardness thresholds through branching random walks 

In the last decades, statistical physics has provided a profound understanding of combinatorial optimisation problems on random input. Yet, many challenges remain open in this field. One of them is the question of algorithmic hardness : for a given problem and input distribution, does there exist a polynomial-time algorithm solving the problem with high probability ? In this talk, we show how (time-inhomogeneous) branching random walks provide an excellent proving ground for studying such questions, allowing for mathematically rigorous answers with relative technical ease. Based on joint works with Louigi Addario-Berry and Fu-Hsuan Ho.

Event tags 

S M T W T F S
26
27
28
29
30
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
31
1
2
3
4
5
6
  1. 2022 (2)
    1. August (1)
    2. April (1)
  2. 2021 (82)
    1. December (5)
    2. November (12)
    3. October (8)
    4. September (5)
    5. July (4)
    6. June (3)
    7. May (6)
    8. April (8)
    9. March (13)
    10. February (7)
    11. January (12)
  3. 2020 (71)
    1. December (2)
    2. November (13)
    3. October (16)
    4. September (7)
    5. August (5)
    6. July (3)
    7. June (2)
    8. May (1)
    9. March (4)
    10. February (4)
    11. January (14)
  4. 2019 (65)
  5. 2018 (44)
  6. 2017 (55)
  7. 2016 (44)
  8. 2015 (37)
  9. 2014 (44)
  10. 2013 (46)
  11. 2012 (44)