A Double Category Theoretic Perspective on Partiality

Mentors: Nathanael Arkor and Bryce Clarke
TA: TBD
Students: TBD

---

Double category theory provides a convenient and expressive setting in which to study functional and relational structure simultaneously. One kind of relation of particular interest is the notion of partial function, which plays important roles in many areas of mathematics and computer science. It might therefore be expected that double categories are good structures with which to study partiality. An existing category theoretic framework for studying partiality is given by the notion of restriction category, which has seen widespread application in computability theory, automata theory, probability theory, algebraic and differential geometry, logic, algebra, and others. There are multiple aspects of restriction category theory that have a double category theoretic flavour, with some explicit connections having been drawn by Paré, and by Cockett and Garner. The goal of this project is to explore the connections between these areas, demonstrating how phenomena observed in restriction category theory are consequences of general results in double category theory.

Readings

• A double category take on restriction categories, Robert Paré
• Restriction categories as enriched categories, Robin Cockett and Richard Garner

Functoriality in Quantum Nonlocality and Interactive Games

Mentor: Martti Karvonen
TA: TBD
Students: TBD

---

Quantum nonlocality is one of the most intriguing and foundational aspects of quantum physics. It is often studied through the mathematical lens of nonlocal games, which provide a framework for capturing and comparing nonlocal correlations. Recent work demonstrates (in passing) that these nonlocal games can be organized into a category, with morphisms corresponding to suitable transformations between games.

Another line of research shows how nonlocal games can be compiled into single-prover interactive games. This project asks: can this compilation be made functorial, possibly preserving further categorical structure? By studying these constructions, we hope to deepen the connections between nonlocality, category theory, and quantum cryptography.

The project will begin with a categorical perspective on quantum nonlocality and contextuality, followed by studying the process of compiling games. The final phase will combine these threads, investigating if and how interactive games admit a categorical treatment that makes the compilation functorial.

Readings

• Closing Bell: Boxing black box simulations in the resource theory of contextuality, Rui Soares Barbosa, Martti Karvonen, Shane Mansfield
• Quantum Advantage from Any Non-Local Game, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, Lisa Yang

Approximating Markov Processes Categorically

Mentor: Prakash Panangaden
TA: TBD
Students: TBD

---

Markov processes are fundamental models of probabilistic systems that have a vast range of applications. They have been studied intensively since the 1930s and have spawned a vast literature. In the 1980’s various researchers (Kozen, Vardi, Larsen and Skou) began studying Markov processes from the point of view of modern programming language theory. In the 1990s new ideas appeared with the incorporation of real-time processes and synchronization (Hillston), model checking (Baier, Kwiatkowska and others) and probabilistic bisimulation on continuous state spaces (Desharnais et al.) as well as metric analogues of bisimulation (Desharnais et al, van Breugel and Worrell). Now these topics are flourishing with many people studying them from categorical viewpoints.

This project concerns an approach to approximating continuous-state Markov processes with finite ones. The approach we will follow uses categorical ideas very heavily and exploits duality theory. It shows how approximation and bisimulation can be understood as morphisms in a suitable category. Existing research has also shown that approximations and bisimulations are morphisms in the same category and how one can re-construct the original process as a suitable limit of the approximants. There are some open issues related to the construction of processes as suitable projective limits which we will investigate in the course of the project. If time permits we can explore the possibility of defining metrics on these Markov processes.

Readings

• Bisimulation for Labeled Markov Processes, Richard Blute, Josee Desharnais, Abbas Edalat, Prakash Panangaden
• Approximating Markov Processes by Averaging, Philippe Chaput, Vincent Danos, Prakash Panangaden, and Gordon Plotkin

Coming Soon