CT-Talk mit Juho Hirvonen, am 2.5.2018 (15:00 | SR4)


Am 2. Mai spricht Juho Hirvonen zum Thema: "Towards a complexity theory for distributed graph algorithms"


Locality of distributed computing is the question of how far information has to propagate in a distributed system. In the last few years, we have seen the emergence of a complexity theory of locality for a large class of natural problems, the locally checkable labelings (LCL). I will survey the key ideas that have led to these developments.
Brandt et al. (STOC 2016) were the first to show that there exists an LCL problem with an "intermediate" complexity. Chang et al. (FOCS 2016) gave two important simulation that show gaps in the complexity hierarchy of LCL problems. Chang and Pettie (FOCS 2017) showed that there also another large gap when solving LCL problems on trees, and conjectured a further gap in the O(poly n) complexity region.
Recently we gave a construction for a family of LCL problems which essentially fill the remaining unknown parts of the complexity landscape, disproving the previous conjecture. The technical part of my talk will consist of trying to illustrate the key ideas behind this construction.


Juho Hirvonen defended his thesis in 2016 at the Aalto University, Finland, supervised by Jukka Suomela. He is currently a postdoctoral researcher at the University of Freiburg in the research group of Fabian Kuhn.