BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Random local algorithms from the graph limits perspective - Endre 
 Csóka (Alfréd Rényi Institute of Mathematics\, Budapest)
DTSTART:20191121T103000Z
DTEND:20191121T113000Z
UID:TALK135193@talks.cam.ac.uk
CONTACT:John Sylvester
DESCRIPTION:We are trying to answer questions such as whether random graph
 s have the least structure among all locally equivalent graphs. More preci
 sely\, we focus on locally defined optimization problems on bounded-degree
  graphs such as finding a large matching or independent set. In random gra
 phs\, our best algorithms for these problems can be approximated by consta
 nt-time randomized distributed algorithms called local algorithms. We give
  an overview about positive and negative results about what can be constru
 cted by them\, including some very recent algorithms and entropy bounds. A
 ll these questions have strong connections to sparse graph limit theory an
 d statistical physics.
LOCATION:Computer Laboratory\, William Gates Building\, Room FW26
END:VEVENT
END:VCALENDAR