The Adjoint School 2020
The 2020 Adjoint School featured projects mentored by Michael Johnson, Nina Otter, Valeria de Paiva, and Michael Shulman. It was organised by Carmen Constantin, Eliana Lorch, and Paolo Perrone. Due to the Covid-19 pandemic, the research week was held online "at" MIT.
Research Projects
Dialectica categories of Petri nets
Mentor: Valeria de Paiva
TA: Jade Master
Students: Elena Di Lavore, Wilmer Leal, Xiaoyan Li, Eigil Rischel
Dialectica categories (also called dialectica spaces) were introduced in the doctoral work of de Paiva, where they were used to model Gödel’s dialectica interpretation, as well as to provide categorical models of Girard’s linear logic. Since then several applications of dialectica categories, have been described. We want to have some more of them. This project is about categories of Petri nets. Petri nets are an extremely popular model of concurrency, both in theory and in practice. They have several descriptions and variations in the literature. One of the interesting problems with Petri nets was to give a compositional theory of them. Brown and Gurr used dialectica categories to model a restricted class of Petri nets. They were joined by de Paiva in a subsequent paper, which generalized the previous work to nets of multiplicity greater than one. Their nets have morphisms corresponding to simulations, which we believe are more flexible than the ones usually considered.
Readings
- A categorical linear framework for Petri nets, C. Brown and D. Gurr
- Categorical multirelations,linear logic and petri nets, Valeria de Paiva
A practical type theory for symmetric monoidal categories
Mentors: Michael Shulman
TA: Paige North
Students: Nuiok Dicaire, Zeinab Galal, Paul Lessard, Sam Speight
Type theories are formal systems allowing us to reason about categorical structures by “treating their objects as if they were sets” in a formal sense. While type theories for cartesian categorical structures are better-known, there are also “linear” type theories for non-cartesian structures. In this project we aim to construct a convenient type theory for reasoning about symmetric monoidal bicategories, which can be used to model many different kinds of open and interconnected systems. We will build on recent results establishing a similar type theory for symmetric monoidal categories as well as coherence theorems for symmetric monoidal bicategories.
Readings
- A practical type theory for symmetric monoidal categories, Michael Shulman
- The Classification of Two-Dimensional Extended Topological Field Theories, Christopher J. Schommer-Pries
Categories of maintainable relations
Mentor: Michael Johnson
TA: Bryce Clark
Students: Emma Chollet, Maurine Songa, Vincent Wang, Gioele Zardini
Relations have many important applications, and correspondingly the category theoretic study of relations is well-developed. Typically, relations from X to Y are defined as subobjects of the product of X and Y, and if X and Y are objects in a regular category C then we can construct a bicategory rel(C) whose morphisms are relations in C. Conversely bicategories that arise as such a rel(C) were studied in a recent ACT School which examined the seminal paper “Cartesian Bicategories I” by Carboni and Walters.
In this project we study (bi)categories of maintainable relations between categories. In this situation, the X and Y of the last paragraph, will be categories, and C will be Cat, the category of (small) categories. Cat is not a regular category, so we need to take an alternative approach to relations that uses equivalence classes of spans in C. Maintainable relations, which are instances of bidirectional transformations (cf lenses), are relations R between categories X and Y with extra structure so that if objects x of X and y of Y are R-related by a specific witness r, and if f: x –> x’ is an arrow of X, then the extra structure gives (functorially) an arrow g: y –> y’ such that x’ and y’ are again R-related, and by a specific witness r’ (cf symmetric delta lenses). Commonly in applications the relation R is called a “consistency relation” and the extra structure is called “consistency restoration” (or in lens terms, change propagation).
This is a rich area with many interesting interactions involving bicategories of spans, lenses (both symmetric and asymmetric), fibrations and generalisations of fibred category theory, as well as direct (and motivating) applications in database design and system interoperation and even machine learning. It is a mix of interesting theoretical questions and concrete applications. We will attack open questions involving exactness properties of categories of maintainable relations, we will seek to understand the interactions with classical work such as that of Carboni and Walters, and we will develop concrete examples of system interactions that are modelled by maintainable relations.
Readings
- Unifying Set-Based, Delta-Based and Edit-Based Lenses , Michael Johnson and Robert Rosebrugh
- Internal lenses as functors and cofunctors, Bryce Clarke
Diagrammatic and algebraic approaches to distances between persistence modules
Mentor: Nina Otter
TAs: Barbara Giunti and Lukas Waas
Students: Max Diefenbach, Feiyang Lin, John Nolan, Anastasios Stefanou
Techniques and ideas from topology are being applied to the study of data with increasing frequency and success. One of the most well-known methods of this type is persistent homology, in which one associates a multiparameter family of spaces to a data set and studies how the holes evolve across the parameter space. The resulting algebraic object is called a persistence module. For one-parameter families of spaces, isomorphism classes of persistence modules can be completely classified by discrete invariants, while in the multiparameter case the situation is more delicate.
Distances between persistence modules are crucial both from a theoretical point of view — for instance, to study the stability of invariants associated to persistence modules —, as well as for applications. The standard distances used for one-parameter persistence modules are L^p distances called Wasserstein distances. For p = ∞ this distance is also called bottleneck distance, and it has arguably been the most used and studied distance for persistence modules. While the original definition is combinatorial, it has equivalent categorical and algebraic formulations called interleaving distance.
In this project we will study different ways to give diagrammatic and algebraic formulations of Wasserstein distances for multiparameter persistence modules. Our motivation will be to investigate the stability of the invariants for multiparameter persistence modules.
Readings
- An algebraic Wasserstein distance for generalized persistence modules, Peter Bubenik, Jonathan Scott, and Donald Stanley
- Stratifying multiparameter persistent homology, Heather A. Harrington, Nina Otter, Hal Schenck, and Ulrike Tillmann