BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Randomised Algorithms &\; Processes
SUMMARY:Random local algorithms from the graph limits pers
pective - Endre Csóka (Alfréd Rényi Institute of M
athematics\, Budapest)
DTSTART;TZID=Europe/London:20191121T103000
DTEND;TZID=Europe/London:20191121T113000
UID:TALK135193AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/135193
DESCRIPTION:We are trying to answer questions such as whether
random graphs have the least structure among all l
ocally equivalent graphs. More precisely\, we focu
s on locally defined optimization problems on boun
ded-degree graphs such as finding a large matching
or independent set. In random graphs\, our best a
lgorithms for these problems can be approximated b
y constant-time randomized distributed algorithms
called local algorithms. We give an overview about
positive and negative results about what can be c
onstructed by them\, including some very recent al
gorithms and entropy bounds. All these questions h
ave strong connections to sparse graph limit theor
y and statistical physics.
LOCATION:Computer Laboratory\, William Gates Building\, Roo
m FW26
CONTACT:John Sylvester
END:VEVENT
END:VCALENDAR