Elena Di Lavore, the PhD student of the Department of Software Science, will defend her PhD thesis „Monoidal Width“ on November 17, 2023, starting at 14:00. The defense will take place in room ICT-638 (Akadeemia tee 15a, ICT building of TalTech) and can be also followed via Zoom.
Compositionality lies at the core of abstraction: local windows on a problem can be combined into a global understanding of it; models and code can be written so that parts can be reused or replaced without breaking the whole; problems can be solved by combining partial solutions. Compositionality may give algorithmic advantages as well. This is the case of divide-and-conquer algorithms, which use the compositional structure of problems to solve them efficiently. Courcelle's theorems are a remarkable example. They rely on a divide-and-conquer algorithm to show that checking monadic second order formulae is tractable on graphs of bounded tree or clique width.
The idea behind fixed-parameter tractability results of this kind is that divide-and-conquer algorithms are efficient on inputs that are structurally simple. In the case of graphs, tree and clique widths measure their structural complexity. When a graph has low width, combining partial solutions on it is tractable. This work aims to bring the techniques from parametrised complexity to monoidal categories.
This thesis introduces monoidal width to measure the structural complexity of morphisms in monoidal categories and investigates some of its properties. By choosing suitable categorical algebras, monoidal width captures tree width and clique width. Monoidal width relies on monoidal decompositions in the same way graph widths rely on graph decompositions and graph expressions. Monoidal decompositions are terms in the language of monoidal categories that specify the compositional structure needed by divide-and-conquer algorithms. A general strategy to obtain fixed-parameter tractability results for problems on monoidal categories highlights the conceptual importance of monoidal width: compositional algorithms make functorial problems tractable on morphisms of bounded monoidal width.
The thesis is published in the Digital Collection of TalTech Library.
Supervisor: prof Pawel Maria Sobocinski.
Opponents:
- prof Samson Abramsky, University College London, UK;
- prof Dan Marsden, University of Nottingham, UK.
Meeting ID: 914 2400 2350
Passcode: 284140