Random local algorithms from the graph limits perspective

Add to your list(s) Download to your calendar using vCal

• Endre Csóka (Alfréd Rényi Institute of Mathematics, Budapest)
• Thursday 21 November 2019, 10:30-11:30
• Computer Laboratory, William Gates Building, Room FW26.

If you have a question about this talk, please contact John Sylvester.

We are trying to answer questions such as whether random graphs have the least structure among all locally equivalent graphs. More precisely, we focus on locally defined optimization problems on bounded-degree graphs such as finding a large matching or independent set. In random graphs, our best algorithms for these problems can be approximated by constant-time randomized distributed algorithms called local algorithms. We give an overview about positive and negative results about what can be constructed by them, including some very recent algorithms and entropy bounds. All these questions have strong connections to sparse graph limit theory and statistical physics.

This talk is part of the Randomised Algorithms & Processes series.

This talk is included in these lists:

• Computer Laboratory, William Gates Building, Room FW26
• Randomised Algorithms & Processes

Note that ex-directory lists are not shown.