Department seminar by Pascal Maillard

Please Note: This seminar will be given online.

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.