Abstract: In this talk, I will introduce a new model of computing model that was presented in “Online Algorithms with Lookaround”, called the online-LOCAL. In this model, the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-T neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space. This model gives a unifying view of locality in four settings: LOCAL model of distributed computing, its sequential counterpart SLOCAL, dynamic algorithms, and online algorithms.
We show that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class - O(log∗ n), Θ(log n), or n^Θ(1) - in all four models. In particular, prior work on the LOCAL model directly generalizes to all four models.
Second, we show that this equivalence does not hold in two-dimensional grids. We show that the locality of the 3-coloring problem is O(log n) in the online-LOCAL model, while it is known to be Ω(√n) in the LOCAL model.
Bio: Darya Melnyk is a postdoc in the distributed algorithms group at Aalto University in Finland. She received her PhD in distributed computing from ETH Zürich in August 2020, and her MSc in mathematics from TU München in 2016. Her research interest is in online algorithms, distributed communication and graph algorithms, voting theory, as well as finding possible connections between the different fields.
