University of Cambridge > Talks.cam > Randomised Algorithms & Processes > Random local algorithms from the graph limits perspective

Random local algorithms from the graph limits perspective

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity