Seminar za teorijsko računarstvo i Seminar za matematičku logiku i osnove matematike

PMF Matematički odsjek
06.06.2022 - 15:00 - 17:00

Na zajedničkom sastanku Seminara za teorijsko računarstvo te Seminara za matematičku logiku i osnove matematike, u ponedjeljak 6. lipnja 2022. u 15 sati,

Goran Žužić (ETH Zurich, Computer Science Department) održat će predavanje pod naslovom:

"Universal optimality in distributed computing and its connections to diverse areas of theoretical computer science".

Sažetak: The modern computation and information processing systems shaping our world have become massively distributed, and a fundamental understanding of distributed algorithmics has never been more important. At the same time, despite 40 years of intense study, we often do not have an adequate understanding of the fundamental barriers that rule out the existence of ultra-fast distributed algorithms. This is true even for the most well-studied problems in computer science–including the shortest path, minimum spanning tree, minimum cut, and many other well-known tasks. In this talk, I will present a high-level overview of a sequence of papers that give a near-complete answer to the above question. Its culmination is the following pie-in-the-sky result called *universal optimality*: for all of the tasks mentioned, there exists a single distributed algorithm that, when run on any communication network G, is provably competitive with the fastest algorithm on G. The pursuit of universal optimality has led to the development of many new connections between distributed computing and other seemingly unrelated areas of theoretical computer science. Curiously, these connections have been mutually-beneficial and have already led to many breakthroughs not only in distributed computing, but also in the theory of metric embedding, information theory, and oblivious packet routing. I will briefly explore these connections.

Predavanje će se održati UŽIVO u zgradi PMF-Matematičkog odsjeka, dvorana 104.

Predavanje če se prenositi i putem sljedećeg Zoom linka:

Pozivaju se članovi oba seminara, studenti diplomskih studija, kao i ostali zainteresirani da se pridruže.

Robert Manger.

Share this