Announcing Em-Cats
The Em-Cats seminar series that was announced a while back is almost about to start! We will be welcoming our first speaker (Jade Master) on Wednesday the 25th of August. Here is some more information about this opening talk.
Nearly six weeks ago, we mentioned that the Em-Cats seminar was entering the final stages of planning. Today I’m happy to write that the first actual talk will be happening this very week!
On Wednesday the 25th of August, Jade Master will be speaking about the universal property of the algebraic path problem, which is a generalisation of the shortest path problem to the setting of graphs weighted in an arbitrary commutative semiring (you can find a more detailed abstract at the end of this post). This first talk will be chaired by Martin Hyland and moderated by Eugenia Cheng.
Eugenia has been working with Jade to prepare and ensure that this talk is an absolutely wonderful one. Indeed, this is one of the main points of the Em-Cats seminar series: Eugenia will be working with each individual speaker, using her experience gained from successfully training graduate students in the past to give accessible talks that benefited both the speaker and the community.
All the talks will be live streamed and recorded, so you can watch them whenever you like. If you’d like to join in the question session, then the live talk will be at 17:00 UTC (Wednesday the 25th of August) on Zoom (with the link accessible from the researchseminars.org page); if you’d like to watch live, you can do so either directly on the Em-Cats webpage or on YouTube.
We look forward to seeing you there!
Jade Master: The Universal Property of the Algebraic Path Problem
The algebraic path problem generalizes the shortest path problem, which studies graphs weighted in the positive real numbers, and asks for the path between a given pair of vertices with the minimum total weight. This path may be computed using an expression built up from the “\mathrm{min}” and “+” of positive real numbers. The algebraic path problem generalizes this from graphs weighted in the positive reals to graphs weighted in an arbitrary commutative semiring R. With appropriate choices of R, many well known problems in optimization, computer science, probability, and computing become instances of the algebraic path problem.
In this talk we will show how solutions to the algebraic path problem are computed with a left adjoint, and this opens the door to reasoning about the algebraic path problem using the techniques of modern category theory. When R is “nice”, a graph weighted in R may be regarded as an R-enriched graph, and the solution to its algebraic path problem is then given by the free R-enriched category on it. The algebraic path problem suffers from combinatorial explosion so that solutions can take a very long time to compute when the size of the graph is large. Therefore, to compute the algebraic path problem efficiently on large graphs, it helps to break it down into smaller sub-problems. The universal property of the algebraic path problem gives insight into the way that solutions to these sub-problems may be glued together to form a solution to the whole, which may be regarded as a “practical” application of abstract category theory.