University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Structured Decompositions: recursive data and recursive algorithms

Structured Decompositions: recursive data and recursive algorithms

Add to your list(s) Download to your calendar using vCal

  • UserBenjamin Bumpus, Glasgow
  • ClockThursday 08 December 2022, 15:00-16:00
  • HouseLTC.

If you have a question about this talk, please contact Johannes Carmesin.

What is recursive structure? And how can we exploit it algorithmically?  In this talk I will give as general an answer as I can to these questions by calling upon the new notion of structured decompositions. This is a category-theoretic formalism that Jade Master, Zoltan Kocsis and I recently introduced which yields a vast generalisation of tree-width to arbitrary categories. I will explain — assuming no prior knowledge at all of category theory — how to make use of structured decompositions for three purposes: (1) defining new tree-width-like invariants, (2) relating these decompositions to each-other via functors and (3) how one might go about proving algorithmic meta-theorems using the language of category theory.  This is ongoing, multidisciplinary work. As such it requires lots people with different types of expertise, so you should consider this talk is an invitation to get involved! 

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.