Seminar for Theoretical Computer...

On Monday, June 6, 2022, 15:00 hours, Goran Žužić (ETH Zurich, Computer Science Department) will hold lecture as part of joint meeting of Seminar for Theoretical Computer Science and Seminar for Mathematical Logics and Foundations of Mathematics titled:

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

Lecture will be held in Lecture room 104, Department of Mathematics.

Lecture will also be streamed via Zoom:

https://zoom.us/j/97325200710?pwd=b2g1ZCtSTjk1dmRQZVVYWTUwOFdMZz09

Seminar members of both seminars, graduate students and other interested audience are invited to attend this interesting lecture.

Abstract: 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.

Author: Božidar Tartaro
News list

Seminars

University of Zagreb

University of Osijek

University of Split

  • Seminar for Topology
  • Seminar for Discrete Mathematics

University of Rijeka

 

Calendar of mathematical events 

Seminar reports (in Croatian)