BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260915T112737Z
UID:Seminar-dept-1238@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20240423T130000
DTEND:20240423T140000
SUMMARY:School Seminar Series
DESCRIPTION:Dr. Dimitrios Los: On the exponential potential for analysing algorithms with dynamic data\n\nIn this talk I will present some techniques to analyse algorithms with dynamic data using exponential potential functions. More specifically, I will show how these techniques can be applied to analyse balanced allocations processes and sorting algorithms where the data is evolving.\n\n\n\nIn the balanced allocations setting we need to allocate $m$ balls into $n$ bins with the aim to minimise the maximum load. In a centralised setting, Round-Robin trivially achieves the optimal maximum load. In a decentralised setting, the $d$-Choice algorithm has proven particularly effective; sampling $d$ bins uniformly at random and allocating to the one with the least load. It is well-known that for $m \gg n$ and $d=1$ the maximum load is $m/n + \Theta(\sqrt{m/n \cdot \log n})$, while for $d = 2$, it is $m/n + \Theta(\log \log n)$, a striking difference known as the ``power of two choices''. I will outline how a small set of techniques can be used to analyse a wide range of algorithms and settings with noise and outdated information.\n\n\n\nIn sorting with evolving data, every step of the comparison-based sorting algorithm is followed by $b$ steps where two elements of adjacent ranks are swapped. The aim is to maintain a permutation that is close in terms of $\ell_1$-distance to the sorted permutation. I will show how a carefully designed exponential potential function can be used to analyse randomised bubble sort, resolving an open problem.\n\n\n\nIf time permits, I will briefly talk about the time complexity of simulating balanced allocation processes.\n\n\n\n(Based on joint work with G. Giakkoupis, M. Kiwi, T. Sauerwald and J. Sylvester)\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1238
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR