IC Colloquium: Understanding Locality: New Techniques and Tight Bounds
Cancelled
Event details
Date | 19.04.2021 |
Hour | 10:00 › 11:00 |
Location | Online |
Category | Conferences - Seminars |
By: Sebastian Brandt - ETH Zurich
IC Faculty candidate
Abstract
Due to the ever-increasing sizes of data sets and real-world networks, computation is becoming more and more distributed. One question that lies at the heart of distributed computation concerns the nature of locality: what can be computed if each entity involved in the computation has access to only a small, local part of the input data, and how fast can such computations be performed? The past five years have seen a tremendous progress on this question, with breakthrough results from various groups of researchers. In this talk, I will survey some of my own contributions to the development of this area.
In particular, the talk will focus on a recent powerful framework for proving time complexity bounds for distributed problems, called round elimination. Despite its conceptual simplicity, this framework has been responsible for a number of recent complexity bounds (in particular fundamental impossibility results) for problems central to distributed computation, such as Maximal Independent Set or Lovász Local Lemma. I will conclude the talk with an overview of what I consider to be some of the most exciting research directions the field of distributed graph algorithms has to offer.
Bio
Sebastian Brandt is a postdoctoral researcher in the Discrete and Distributed Algorithms Group at ETH Zurich. He received his PhD from ETH in 2018, under the guidance of Roger Wattenhofer. Sebastian is working on distributed and parallel algorithms, with a special focus on locality and how it affects computation in general. In 2019, he received a FOCS Best Paper Award for work on locality lower bounds.
More information
IC Faculty candidate
Abstract
Due to the ever-increasing sizes of data sets and real-world networks, computation is becoming more and more distributed. One question that lies at the heart of distributed computation concerns the nature of locality: what can be computed if each entity involved in the computation has access to only a small, local part of the input data, and how fast can such computations be performed? The past five years have seen a tremendous progress on this question, with breakthrough results from various groups of researchers. In this talk, I will survey some of my own contributions to the development of this area.
In particular, the talk will focus on a recent powerful framework for proving time complexity bounds for distributed problems, called round elimination. Despite its conceptual simplicity, this framework has been responsible for a number of recent complexity bounds (in particular fundamental impossibility results) for problems central to distributed computation, such as Maximal Independent Set or Lovász Local Lemma. I will conclude the talk with an overview of what I consider to be some of the most exciting research directions the field of distributed graph algorithms has to offer.
Bio
Sebastian Brandt is a postdoctoral researcher in the Discrete and Distributed Algorithms Group at ETH Zurich. He received his PhD from ETH in 2018, under the guidance of Roger Wattenhofer. Sebastian is working on distributed and parallel algorithms, with a special focus on locality and how it affects computation in general. In 2019, he received a FOCS Best Paper Award for work on locality lower bounds.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- George Candea