BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Understanding Locality: New Techniques and Tight Bo
 unds
DTSTART:20210419T100000
DTEND:20210419T110000
DTSTAMP:20260407T183623Z
UID:3680e9f6e36734a15bb8c688fac3a3b8d1c1ce5fcedc716e4d052ced
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Sebastian Brandt - ETH Zurich\nIC Faculty candidate\n\nAbs
 tract\nDue to the ever-increasing sizes of data sets and real-world networ
 ks\, computation is becoming more and more distributed. One question that 
 lies at the heart of distributed computation concerns the nature of locali
 ty: what can be computed if each entity involved in the computation has ac
 cess to only a small\, local part of the input data\, and how fast can suc
 h computations be performed? The past five years have seen a tremendous pr
 ogress 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.\n\nIn particular\, the talk will focus on a
  recent powerful framework for proving time complexity bounds for distribu
 ted problems\, called round elimination. Despite its conceptual simplicity
 \, this framework has been responsible for a number of recent complexity b
 ounds (in particular fundamental impossibility results) for problems centr
 al 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 distribu
 ted graph algorithms has to offer.\n\nBio\nSebastian Brandt is a postdocto
 ral researcher in the Discrete and Distributed Algorithms Group at ETH Zur
 ich. He received his PhD from ETH in 2018\, under the guidance of Roger Wa
 ttenhofer. Sebastian is working on distributed and parallel algorithms\, w
 ith 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.\n\nMore information
LOCATION:https://epfl.zoom.us/j/81476095732?pwd=aGt2NkdOTVVQTmFmSXl1RUlQV0
 9VZz09
STATUS:CANCELLED
END:VEVENT
END:VCALENDAR