Department seminar by Pascal Maillard

Wednesday, October 20, 2021 11:00 am - 11:00 am EDT (GMT -04:00)

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.