Petra Berenbrink: Optimal Time and Space Leader Election in Population Protocols

Population protocols are a model of distributed computing, where n agents with limited computational power and memory interact randomly, in order to jointly perform a global task. A fundamental problem in this setting is that of leader election, where all agents start from the same state, and they seek to reach and maintain a global state where exactly one agent is in a dedicated leader state. We establish that if agents have Omega(\log\log n) states, the expected time complexity of leader election is Theta(n \log n). Unlike existing protocols, ours does not decrease the set of candidate leaders monotonically. Our protocol has both optimal time and space complexity. Joint work with George Giakkoupis and Peter Kling

Contact algorithms.complexity@dur.ac.uk for more information about this event.

Robert Segal: Myth for the Twenty-First century: Winnicott applied to myth

Contact jonathan.miles-watson@durham.ac.uk, m.j.guest@durham.ac.uk for more information about this event.

Netan Dogra: Wieferich statistics, p-adic integrals and rational points on curves.

A Wieferich prime is a prime number p such that 2^(p-1) is congruent to 1 modulo p^2. These numbers originally arose in the context of Fermat's last theorem. At present very little is known about them, although there are some conjectures. One can analogously define Wieferich primes for 3, or 5, or for a point on an abelian variety. In this talk I will explain what Wieferich primes for abelian varieties have to do with p-adic integrals and rational points on curves, and will also describe some (unconditional) results on the heights of rational points on higher genus curves.

Contact pankaj.vishe@durham.ac.uk, athanasios.bouganis@durham.ac.uk, herbert.gangl@durham.ac.uk for more information about this event.

Dr Anna Rowlands: Pius XII's Christmas Messages

Contact ccs.admin@durham.ac.uk for more information about this event.