Fecha y lugar: Miércoles 20 de agosto, 12:00hrs, Sala Seminario Felipe Álvarez (5to piso)
Expositor 1: Benjamín Jauregui (Universidad de Chile)
Title: “Distributed Courcelle’s Theorem.”
Abstract: Algorithmic meta-theorems show that broad families of graph problems, when expressible in a suitable logic, can be solved efficiently on graph classes with specific structural properties. A central example in sequential algorithms is Courcelle’s theorem, which establishes that all properties definable in Monadic Second-Order logic (MSO) are decidable in linear time on graphs of bounded treewidth.
In this talk, I will give an introduction to distributed computing and highlight the main challenges in the design of distributed algorithms. I will then present a distributed analogue of Courcelle’s theorem in the distributed CONGEST model: for any MSO formula φ and any constant k, there exists a distributed CONGEST algorithm that, given an input communication network G of treewidth at most k and diameter D, decides whether G satisfies property φ in Õ(D) rounds.
Invitación link zoom:
https://uchile.zoom.us/j/93417604828?pwd=eSHafQqVcAegttXqKH3swXZsMseRrn.1