"False"
Skip to content
printicon
Main menu hidden.

Twin-width IV and V

Thu
2
Feb
Time Thursday 2 February, 2023 at 14:15 - 15:15
Place Zoom

Twin-width IV and V: ordered structures, modular counting and matrix multiplication

Abstract: Twin-width is a graph parameter recently discovered by Bonnet, Kim, Thomassé and Watrigant that aims at generalizing and unifying many previous notions from parameterized complexity. The original article introducing twin-width was the starting point of a series of papers setting the basis of the theory of twin-width.

In this presentation, I will first give you a brief introduction to twin-width, and state the main results and questions. Then I will focus on ordered graphs, (i.e. graphs with a total order on their vertices) and show you that in this case there are many different ways to characterize twin-width boundedness, going from enumerative combinatorics to logics. In particular, from these characterizations we will see that there exists an FPT-algorithm to approximate the twin-width of ordered graphs, which is still not known to exist in the general case. In the remaining time, as an example of application I will explain you how to derive an efficient algorithm to compute in time Oq,t(n2 log(n)) the product of two matrices of twin-width t over the finite field Fq.     

Joint work with Edouard Bonnet, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé and Szymon Toruńczyk.

To receive the Zoom link, please contact Victor Falgas Ravry

Event type: Seminar

Speaker: Ugo Giocanti, ENS Lyon

Contact
Victor Falgas Ravry
Read about Victor Falgas Ravry