Locality lower bounds through round elimination
Date
Monday, February 3, 2020 14:30 - 16:00
Speaker
Jukka Suomela (Aalto University)
Location
Heinzel Seminar Room / Office Bldg West (I21.EG.101)
Series
Seminar/Talk
Tags
Mathematics and CS Seminar
Host
Dan Alistarh
Contact
A fundamental concept in distributed computing is locality: how far does an individual node need to see in a large network in order to choose its own part of the solution? In this talk I will introduce a new technique for proving lower bounds on locality, round elimination, and show how it can be applied in the study of classical graph problems such as maximal matchings and maximal independent sets.