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

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹ️ Information

Random local algorithms from the graph limits perspective

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Lecture Theatre 4, Cambridge University Engineering Department, Trumpington Street, Cambridge CB2 1PZ Seminar Room 2, CMS Gatehouse Adrian House Seminar Room, Trinity College

Other talks

Formal Dinner at Selwyn College Title and abstract tba Title TBC How bubble acoustics can help in three apocalypses Title to be confirmed CSAR lecture: Decarbonizing road freight (TBC)
 

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