Applied Category Theory 2021 — Call for Papers

16 April, 2021


The deadline for submitting papers is coming up soon: May 10th.

Fourth Annual International Conference on Applied Category Theory (ACT 2021), July 12–16, 2021, online and at the Computer Laboratory of the University of Cambridge.

Plans to run ACT 2021 as one of the first physical conferences post-lockdown are progressing well. Consider going to Cambridge! Financial support is available for students and junior researchers.

Applied category theory is a topic of interest for a growing community of researchers, interested in studying many different kinds of systems using category-theoretic tools. These systems are found across computer science, mathematics, and physics, as well as in social science, linguistics, cognition, and neuroscience. The background and experience of our members is as varied as the systems being studied. The goal of the Applied Category Theory conference series is to bring researchers together, disseminate the latest results, and facilitate further development of the field.

We accept submissions of both original research papers, and work accepted/submitted/ published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume. The keynote addresses will be drawn from the best accepted papers. The conference will include an industry showcase event.

We hope to run the conference as a hybrid event, with physical attendees present in Cambridge, and other participants taking part online. However, due to the state of the pandemic, the possibility of in-person attendance is not yet confirmed. Please do not book your travel or hotel accommodation yet.

Financial support

We are able to offer financial support to PhD students and junior researchers. Full guidance is on the webpage.

Important dates (all in 2021)

• Submission Deadline: Monday 10 May
• Author Notification: Monday 7 June
• Financial Support Application Deadline: Monday 7 June
• Financial Support Notification: Tuesday 8 June
• Priority Physical Registration Opens: Wednesday 9 June
• Ordinary Physical Registration Opens: Monday 13 June
• Reserved Accommodation Booking Deadline: Monday 13 June
• Adjoint School: Monday 5 to Friday 9 July
• Main Conference: Monday 12 to Friday 16 July

Submissions

The following two types of submissions are accepted:

Proceedings Track. Original contributions of high-quality work consisting of an extended abstract, up to 12 pages, that provides evidence of results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submission of work-in-progress is encouraged, but it must be more substantial than a research proposal.

Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure that these pages contain sufficient evidence of the quality and rigour of your work.

Papers in the two tracks will be reviewed against the same standards of quality. Since ACT is an interdisciplinary conference, we use two tracks to accommodate the publishing conventions of different disciplines. For example, those from a Computer Science background may prefer the Proceedings Track, while those from a Mathematics, Physics or other background may prefer the Non-Proceedings Track. However, authors from any background are free to choose the track that they prefer, and submissions may be moved from the Proceedings Track to the Non-Proceedings Track at any time at the request of the authors.

Contributions must be submitted in PDF format. Submissions to the Proceedings Track must be prepared with LaTeX, using the EPTCS style files available at http://style.eptcs.org.

The submission link will soon be available on the ACT2021 web page: https://www.cl.cam.ac.uk/events/act2021

Program Committee

Chair:

• Kohei Kishida, University of Illinois, Urbana-Champaign

Members:

• Richard Blute, University of Ottawa
• Spencer Breiner, NIST
• Daniel Cicala, University of New Haven
• Robin Cockett, University of Calgary
• Bob Coecke, Cambridge Quantum Computing
• Geoffrey Cruttwell, Mount Allison University
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Jonas Frey, Carnegie Mellon University
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Fabrizio Romano Genovese, Statebox
• Helle Hvid Hansen, University of Groningen
• Jules Hedges, University of Strathclyde
• Chris Heunen, University of Edinburgh
• Alex Hoffnung, Bridgewater
• Martti Karvonen, University of Ottawa
• Kohei Kishida, University of Illinois, Urbana -Champaign (chair)
• Martha Lewis, University of Bristol
• Bert Lindenhovius, Johannes Kepler University Linz
• Ben MacAdam, University of Calgary
• Dan Marsden, University of Oxford
• Jade Master, University of California, Riverside
• Joe Moeller, NIST
• Koko Muroya, Kyoto University
• Simona Paoli, University of Leicester
• Daniela Petrisan, Université de Paris, IRIF
• Mehrnoosh Sadrzadeh, University College London
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
• David Spivak, MIT and Topos Institute
• Joshua Tan, University of Oxford
• Dmitry Vagner
• Jamie Vicary, University of Cambridge
• John van de Wetering, Radboud University Nijmegen
• Vladimir Zamdzhiev, Inria, LORIA, Université de Lorraine
• Maaike Zwart


Emerging Researchers in Category Theory

11 March, 2021

 

Eugenia Cheng is an expert on giving clear, fun math talks.

Now you can take a free class from her on how to give clear, fun math talks!

You need to be a grad student in category theory—and priority will be given to those who aren’t at fancy schools, etc.

Her course is called the Emerging Researchers in Category Theory Virtual Seminar, or Em-Cats for short. You can apply for it here:

https://topos.site/em-cats/

The first round of applications is due April 30th. It looks pretty cool, and knowing Eugenia, you’ll get a lot of help on giving talks.

Aims

The aims are, broadly:

• Help the next generation of category theorists become wonderful speakers.
• Make use of the virtual possibilities, and give opportunities to graduate students in places where there is not a category theory group or local seminar they can usefully speak in.
• Give an opportunity to graduate students to have a global audience, especially giving more visibility to students from less famous/large groups.
• Make a general opportunity for community among category theorists who are more isolated than those with local groups.
• Make a series of truly intelligible talks, which we hope students and researchers around the world will enjoy and appreciate.

Talk Preparation and Guidelines

Eugenia Cheng has experience with training graduate students in giving talks, from when she ran a similar seminar for graduate students at the University of Sheffield. Everyone did indeed give an excellent talk.

We ask that all Em-Cats speakers are willing to work with Eugenia and follow her advice. The guidelines document outlines what she believes constitutes a good talk. We acknowledge that this is to some extent a matter of opinion, but these are the guidelines for this particular seminar. Eugenia is confident that with her assistance everyone who wishes to do so will be able to give an excellent, accessible talk, and that this will benefit both the speaker and the community.


Applied Category Theory 2021

17 February, 2021


The big annual applied category theory conference is coming! It’s the fourth one: the first three were at Leiden, Oxford and (virtually) MIT. This one will be online and also, with luck, in person—but don’t make your travel arrangements just yet:

Fourth Annual International Conference on Applied Category Theory (ACT 2021), 12–16 July 2021, online and at the Computer Laboratory of the University of Cambridge.

It will take place shortly after the Applied Category Theory Adjoint School, which will—with luck—culminate in a meeting 5–9 July at the same location.

You can now submit a paper! As in a computer science conference, that’s how you get to give a talk. For more details, read on.

Overview

Applied category theory is a topic of interest for a growing community of researchers, interested in studying many different kinds of systems using category-theoretic tools. These systems are found across computer science, mathematics, and physics, as well as in social science, linguistics, cognition, and neuroscience. The background and experience of our members is as varied as the systems being studied. The goal of the Applied Category Theory conference series is to bring researchers
together, disseminate the latest results, and facilitate further development of the field.

We accept submissions of both original research papers, and work accepted/submitted/ published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume. The keynote addresses will be drawn from the best accepted papers. The conference will include an industry showcase event.

We hope to run the conference as a hybrid event, with physical attendees present in Cambridge, and other participants taking part online. However, due to the state of the pandemic, the possibility of in-person attendance is not yet confirmed. Please do not book your travel or hotel accommodation yet.

Important dates (all in 2021)

• Submission of contributed papers: Monday 10 May

• Acceptance/rejection notification: Monday 7 June

• Adjoint school: Monday 5 July to Friday 9 July

• Main conference: Monday 12 July to Friday 16 July

Submissions

The following two types of submissions are accepted:

• Proceedings Track. Original contributions of high-quality work consisting of an extended abstract, up to 12 pages, that provides evidence of results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submission of work-in-progress is encouraged, but it must be more substantial than a research proposal.

• Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure that these pages contain sufficient evidence of the quality and rigour of your work.

Papers in the two tracks will be reviewed against the same standards of quality. Since ACT is an interdisciplinary conference, we use two tracks to accommodate the publishing conventions of different disciplines. For example, those from a Computer Science background may prefer the Proceedings Track, while those from a Mathematics, Physics or other background may prefer the Non-Proceedings Track. However, authors from any background are free to choose the track that they prefer, and submissions may be moved from the Proceedings Track to the Non-Proceedings Track at any time at the request of the authors.

Contributions must be submitted in PDF format. Submissions to the Proceedings Track must be prepared with LaTeX, using the EPTCS style files available at

http://style.eptcs.org

The submission link will soon be available on the ACT2021 web page:

https://www.cl.cam.ac.uk/events/act2021

Program committee

Chair: Kohei Kishida, University of Illinois, Urbana-Champaign

The full program committee will be announced soon.

Local organizers

• Lukas Heidemann, University of Oxford
• Nick Hu, University of Oxford
• Ioannis Markakis, University of Cambridge
• Alex Rice, University of Cambridge
• Calin Tataru, University of Cambridge
• Jamie Vicary, University of Cambridge

Steering committee

• John Baez, University of California Riverside and Centre for Quantum Technologies
• Bob Coecke, Cambridge Quantum Computing
• Dorette Pronk, Dalhousie University
• David Spivak, Topos Institute


Applied Category Theory 2021 — Adjoint School

2 January, 2021

Do you want to get involved in applied category theory? Are you willing to do a lot of work and learn a lot? Then this is for you:

Applied Category Theory 2021 — Adjoint School. Applications due Friday 29 January 2021. Organized by David Jaz Myers, Sophie Libkind, and Brendan Fong.

There are four projects to work on with great mentors. You can see descriptions of them below!

By the way, it’s not yet clear if there will be an in-person component to this school —but if there is, it will happen at the University of Cambridge. ACT2021 is being organized by Jamie Vicary, who teaches in the computer science department there.

Who should apply?

Anyone, from anywhere in the world, who is interested in applying category-theoretic methods to problems outside of pure mathematics. This is emphatically not restricted to math students, but one should be comfortable working with mathematics. Knowledge of basic category-theoretic language—the definition of monoidal category for example—is encouraged.

We will consider advanced undergraduates, PhD students, post-docs, as well as people working outside of academia. Members of groups which are underrepresented in the mathematics and computer science communities are especially encouraged to apply.

School overview

Participants are divided into four-person project teams. Each project is guided by a mentor and a TA. The Adjoint School has two main components: an Online Seminar that meets regularly between February and June, and an in-person Research Week in Cambridge, UK on July 5–9.

During the online seminar, we will read, discuss, and respond to papers chosen by the project mentors. Every other week, a pair of participants will present a paper which will be followed by a group discussion. Leading up to this presentation, study groups will meet to digest the reading in progress, and students will submit reading responses. After the presentation, the presenters will summarize the paper into a blog post for The n-Category Cafe.

The in-person research week will be held the week prior to the International Conference on Applied Category Theory and in the same location. During the week, participants work intensively with their research group under the guidance of their mentor. Projects from the Adjoint School will be presented during this conference. Both components of the school aim to develop a sense of belonging and camaraderie in students so that they can fully participate in the conference, for example by attending talks and chatting with other conference goers.

Projects to choose from

Here are the projects.

Topic: Categorical and computational aspects of C-sets

Mentors: James Fairbanks and Evan Patterson

Description: Applied category theory includes major threads of inquiry into monoidal categories and hypergraph categories for describing systems in terms of processes or networks of interacting components. Structured cospans are an important class of hypergraph categories. For example, Petri net-structured cospans are models of concurrent processes in chemistry, epidemiology, and computer science. When the structured cospans are given by C-sets (also known as co-presheaves), generic software can be implemented using the mathematics of functor categories. We will study mathematical and computational aspects of these categorical constructions, as well as applications to scientific computing.

Readings:

Structured cospans, Baez and Courser.

An algebra of open dynamical systems on the operad of wiring diagrams, Vagner, Spivak, and Lerman.

Topic: The ubiquity of enriched profunctor nuclei

Mentor: Simon Willerton

Description: In 1964, Isbell developed a nice universal embedding for metric spaces: the tight span. In 1966, Isbell developed a duality for presheaves. These are both closely related to enriched profunctor nuclei, but the connection wasn’t spotted for 40 years. Since then, many constructions in mathematics have been observed to be enriched profunctor nuclei too, such as the fuzzy/formal concept lattice, tropical convex hull, and the Legendre–Fenchel transform. We’ll explore the world of enriched profunctor nuclei, perhaps seeking out further useful examples.

Readings:

The Legendre–Fenchel transform from a category theoretic perspective, Willerton.

On the fuzzy concept complex (chapters 2-3), Elliot.

Topic: Double categories in applied category theory

Mentor: Simona Paoli

Description: Bicategories and double categories (and their symmetric monoidal versions) have recently featured in applied category theory: for instance, structured cospans and decorated cospans have been used to model several examples, such as electric circuits, Petri nets and chemical reaction networks.

An approach to bicategories and double categories is available in higher category theory through models that do not require a direct checking of the coherence axioms, such as the Segal-type models. We aim to revisit the structures used in applications in the light of these approaches, in the hope to facilitate the construction of new examples of interest in applications.

Readings:

Structured cospans, Baez and Courser.

A double categorical model of weak 2-categories, Paoli and Pronk.

and introductory chapters of:

Simplicial Methods for Higher Categories: Segal-type Models of Weak n-Categories, Paoli.

Topic: Extensions of coalgebraic dynamic logic

Mentors: Helle Hvid Hansen and Clemens Kupke

Description: Coalgebra is a branch of category theory in which different types of state-based systems are studied in a uniform framework, parametric in an endofunctor F:C → C that specifies the system type. Many of the systems that arise in computer science, including deterministic/nondeterministic/weighted/probabilistic automata, labelled transition systems, Markov chains, Kripke models and neighbourhood structures, can be modeled as F-coalgebras. Once we recognise that a class of systems are coalgebras, we obtain general coalgebraic notions of morphism, bisimulation, coinduction and observable behaviour.

Modal logics are well-known formalisms for specifying properties of state-based systems, and one of the central contributions of coalgebra has been to show that modal logics for coalgebras can be developed in the general parametric setting, and many results can be proved at the abstract level of coalgebras. This area is called coalgebraic modal logic.

In this project, we will focus on coalgebraic dynamic logic, a coalgebraic framework that encompasses Propositional Dynamic Logic (PDL) and Parikh’s Game Logic. The aim is to extend coalgebraic dynamic logic to system types with probabilities. As a concrete starting point, we aim to give a coalgebraic account of stochastic game logic, and apply the coalgebraic framework to prove new expressiveness and completeness results.

Participants in this project would ideally have some prior knowledge of modal logic and PDL, as well as some familiarity with monads.

Readings:

Parts of these:

Universal coalgebra: a theory of systems, Rutten.

Coalgebraic semantics of modal logics: an overview, Kupke and Pattinson.

Strong completeness of iteration-free coalgebraic dynamic logics, Hansen, Kupke, and Leale.


Category Theory Calendar

6 April, 2020

There are now enough online events in category theory that a calendar is needed. And here it is!

https://teamup.com/ksfss6k4j1bxc8vztb

It should show the times in your time zone, at least if you don’t prevent it from getting that information.


Category Theory Community Server

25 March, 2020

My student Christian Williams has started a community server for category theory, computer science, logic, as well as general science and industry. In just a few days, it has grown into a large and lively place, with people of many backgrounds and interests. Please feel free to join!

Register here:

https://categorytheory.zulipchat.com/join/eroxtuhxmr6oy6daqfdxtq2e/

(this link will expire in a while) and from then on you can just go here:

http://categorytheory.zulipchat.com

If the link for registration has expired, just let me know and I’ll revive it.

\;
category-theory-banner-light


Applied Category Theory 2020 (Part 2)

23 March, 2020

Due to the coronavirus outbreak, many universities are moving activities online. This is a great opportunity to open up ACT2020 to a broader audience, with speakers from around the world.

The conference will take place July 6-10 online, coordinated by organizers in Boston USA. Each day there will be around six hours of live talks, which will be a bit more spaced out than usual to accommodate the different time zones of our speakers. All the talks will be both live streamed and recorded on YouTube. We will also have chat rooms and video chats in which participants can discuss various themes in applied category theory.

We will give more details as they become available and post updates on our official webpage:

http://act2020.mit.edu

Since there is no need to book travel, we were able to postpone the acceptance notification, and hence the submission deadline. If you would like to speak, please prepare an abstract or a conference paper according to the instructions here:

http://act2020.mit.edu/#papers

Important dates (all in 2020)

• Submission of contributed papers: May 10
• Acceptance/Rejection notification: June 7
• Tutorial day: July 5
• Main conference: July 6-10

Registration will now be free; please register for the conference ahead of time here:

http://act2020.mit.edu/#registration

We will send registering participants links to the live stream, the recordings, and the chat rooms, and we’ll use the list to inform participants of any changes.

Submissions

To give a talk at ACT2020, you have to submit a paper. You can submit either original research papers or extended abstracts of work submitted/accepted/published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume.

Here’s how to submit papers. Two types of submissions are accepted, which will be reviewed to the same standards:

Proceedings Track. Original contributions of high quality work consisting of a 5–12 page extended abstract that provides evidence for results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submissions of works in progress are encouraged, but must be more substantial than a research proposal.

Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure these pages contain sufficient evidence of the quality and rigor of your work.

Submissions should be prepared using LaTeX, and must be submitted in PDF format. Submission is currently open, and can be perfomed at the following web page:

https://easychair.org/conferences/?conf=act2020

One or more best paper awards may be given out at the discretion of the PC chairs. Selected contributions will be offered extended keynote slots in the program.

Organizers

Here are the local organizers:

• Destiny Chen (administration)
• Brendan Fong
• David Jaz Myers (logistics)
• Paolo Perrone (publicity)
• David Spivak

Here is the committee running the school:

• Carmen Constantin
• Eliana Lorch
• Paolo Perrone

Here is the steering committee:

• John Baez
• Bob Coecke
• David Spivak
• Christina Vasilakopoulou

Here is the program committee:

• Mathieu Anel, CMU
• John Baez, University of California, Riverside
• Richard Blute, University of Ottawa
• Tai-Danae Bradley, City University of New York
• Andrea Censi, ETC Zurich
• Bob Coecke, University of Oxford
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Ross Duncan, University of Strathclyde
• Eric Finster, University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Richard Garner, Macquarie University
• Fabrizio Romano Genovese, Statebox
• Amar Hadzihasanovic, IRIF, Université de Paris
• Helle Hvid Hansen, Delft University of Technology
• Jules Hedges, Max Planck Institute for Mathematics in the Sciences
• Kathryn Hess Bellwald, Ecole Polytechnique Fédérale de Lausanne
• Chris Heunen, The University of Edinburgh
• Joachim Kock, UAB
• Tom Leinster, The University of Edinburgh
• Martha Lewis, University of Amsterdam
• Daniel R. Licata, Wesleyan University
• David Jaz Myers, Johns Hopkins University
• Paolo Perrone, MIT
• Vaughan Pratt, Stanford University
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
David I. Spivak, MIT (co-chair)
• Walter Tholen, York University
• Todd Trimble, Western Connecticut State University
Jamie Vicary, University of Birmingham (co-chair)
• Maaike Zwart, University of Oxford


Applied Category Theory 2020 (Part 1)

1 March, 2020

Here’s the big annual conference on applied category theory:

ACT2020, 2020 July 6–10, online worldwide. Organized by Brendan Fong and David Spivak.

This happens right after the applied category theory school, which will take place June 29 – July 3. There will also be a tutorial day on Sunday July 5, with talks by Paolo Perrone, Emily Riehl, David Spivak and others.

To give a talk at ACT2020, you have to submit a paper. You can submit either original research papers or extended abstracts of work submitted/accepted/published elsewhere. Accepted original research papers will be invited for publication in a proceedings volume. Some contributions will be invited to become keynote addresses, and best paper awards may also be given. The conference will also include a business showcase.

Here’s how to submit papers. Two types of submissions are accepted, which will be reviewed to the same standards:

Proceedings Track. Original contributions of high quality work consisting of a 5–12 page extended abstract that provides evidence for results of genuine interest, and with enough detail to allow the program committee to assess the merits of the work. Submissions of works in progress are encouraged, but must be more substantial than a research proposal.

Non-Proceedings Track. Descriptions of high-quality work submitted or published elsewhere will also be considered, provided the work is recent and relevant to the conference. The work may be of any length, but the program committee members may only look at the first 3 pages of the submission, so you should ensure these pages contain sufficient evidence of the quality and rigor of your work.

Submissions should be prepared using LaTeX, and must be submitted in PDF format. Submission is currently open, and can be perfomed at the following web page:

https://easychair.org/conferences/?conf=act2020

Here are some important dates, all in 2020:

• Submission of contributed papers: April 26
• Acceptance/rejection notification: May 17
• Early bird registration deadline: May 20
• Final registration deadline: June 26
• Tutorial day: July 5
• Main conference: July 6–10

Here is the program committee:

• Mathieu Anel, CMU
• John Baez, University of California, Riverside
• Richard Blute, University of Ottawa
• Tai-Danae Bradley, City University of New York
• Andrea Censi, ETC Zurich
• Bob Coecke, University of Oxford
• Valeria de Paiva, Samsung Research America and University of Birmingham
• Ross Duncan, University of Strathclyde
• Eric Finster, University of Birmingham
• Brendan Fong, Massachusetts Institute of Technology
• Tobias Fritz, Perimeter Institute for Theoretical Physics
• Richard Garner, Macquarie University
• Fabrizio Romano Genovese, Statebox
• Amar Hadzihasanovic, IRIF, Université de Paris
• Helle Hvid Hansen, Delft University of Technology
• Jules Hedges, Max Planck Institute for Mathematics in the Sciences
• Kathryn Hess Bellwald, Ecole Polytechnique Fédérale de Lausanne
• Chris Heunen, The University of Edinburgh
• Joachim Kock, UAB
• Tom Leinster, The University of Edinburgh
• Martha Lewis, University of Amsterdam
• Daniel R. Licata, Wesleyan University
• David Jaz Myers, Johns Hopkins University
• Paolo Perrone, MIT
• Vaughan Pratt, Stanford University
• Peter Selinger, Dalhousie University
• Michael Shulman, University of San Diego
David I. Spivak, MIT (co-chair)
• Walter Tholen, York University
• Todd Trimble, Western Connecticut State University
Jamie Vicary, University of Birmingham (co-chair)
• Maaike Zwart, University of Oxford

Here is the steering committee:

• John Baez
• Bob Coecke
• David Spivak
• Christina Vasilakopoulou

Here is the committee running the school:

• Carmen Constantin
• Eliana Lorch
• Paolo Perrone

And here are the local organizers:

• Destiny Chen (administration)
• Brendan Fong
• David Jaz Myers (logistics)
• Paolo Perrone (publicity)
• David Spivak

More news will follow!


Applied Category Theory at NIST (Part 3)

22 February, 2020

Sadly, this workshop has been cancelled due to the coronavirus pandemic. It may be postponed to a later date.

My former student Blake Pollard is working at the National Institute of Standards and Technology. He’s working with Spencer Breiner and Eswaran Subrahmanian, who are big advocates of using category theory to organize design and manufacturing processes. In the spring of 2018 they had a workshop on applied category theory with a lot of honchos from industry and government in attendance—you can see videos by clicking the link.

This spring they’re having another workshop on this topic!

Applied Category Theory Workshop, April 8-9, 2020, National Institute of Standards and Technology, Gaithersburg, Maryland. Organized by Spencer Breiner, Blake Pollard and Eswaran Subrahmanian.

The focus of this workshop in on fostering the development of tooling and use-cases supporting the applied category theory community. We are particularly interested in bringing together practitioners who are engaged with susceptible domains as well as those involved in the implementation, support, and utilization of software and other tools. There will be a number of talks/demos showcasing existing approaches as well as ample time for discussion.

Here are the speakers listed so far:

• John Baez, University of California, Riverside

• Arquimedes Canedo, Siemens

• Daniel Cicala, New Haven University

• James Fairbanks, Georgia Tech Research Institute

• Jules Hedges, Max Planck Institute for the Mathematical Sciences

• Jelle Herold, Statebox

• Evan Patterson, Stanford University

• Qunfen Qi, University of Huddersfield

• Christian Williams, University of California, Riverside

• Ryan Wisnesky, Conexus.ai

I’ll also be giving a separate talk on “ecotechnology” at NIST on Friday April 10th; more about that later!


The Category Theory Behind UMAP

10 February, 2020

An interesting situation has arisen. Some people working on applied category theory have been seeking a ‘killer app’: that is, an application of category theory to practical tasks that would be so compelling it would force the world to admit categories are useful. Meanwhile, the UMAP algorithm, based to some extent on category theory, has become very important in genomics:

• Leland McInnes, John Healy and James Melville, UMAP: uniform manifold approximation and projection for dimension reduction.

But while practitioners have embraced the algorithm, they’re still puzzled by its category-theoretic underpinnings, which are discussed in Section 2 of the paper. (You can read the remaining sections, which describe the algorithm quite concretely, without understanding Section 2.)

I first heard of this situation on Twitter when James Nichols wrote:

Wow! My first sighting of applied category theory: the UMAP algorithm. I’m a category novice, but the resulting adjacency-graph algorithm is v simple, so surely the theory boils down to reasonably simple arguments in topology/Riemannian geometry?

Do any of you prolific ACT tweeters know much about UMAP? I understand the gist of the linked paper, but not say why we need category theory to define this “fuzzy topology” concept, as opposed to some other analytic defn.

Junhyong Kim added:

What was gained by CT for UMAP? (honest question, not trying to be snarky)

Leland McInnes, one of the inventors of UMAP, responded:

It is my math background, how I think about the problem, and how the algorithm was derived. It wasn’t something that was added, but rather something that was always there—for me at least. In that sense what was gained was the algorithm.

I don’t really understand UMAP; for a good introduction to it see the original paper above and also this:

• Nikolay Oskolkov, How Exactly UMAP Works—and Why Exactly It Is Better Than tSNE, 3 October 2019.

tSNE is an older algorithm for taking clouds of data points in high dimensions and mapping them down to fewer dimensions so we can understand what’s going on. From the viewpoint of those working on genomics, the main good thing about UMAP is that it solves a bunch of problems that plagued tSNE. Oskolkov explains what these problems are and how UMAP deals with them. But he also alludes to the funny disconnect between these practicalities and the underlying theory:

My first impression when I heard about UMAP was that this was a completely novel and interesting dimension reduction technique which is based on solid mathematical principles and hence very different from tSNE which is a pure Machine Learning semi-empirical algorithm. My colleagues from Biology told me that the original UMAP paper was “too mathematical”, and looking at the Section 2 of the paper I was very happy to see strict and accurate mathematics finally coming to Life and Data Science. However, reading the UMAP docs and watching Leland McInnes talk at SciPy 2018, I got puzzled and felt like UMAP was another neighbor graph technique which is so similar to tSNE that I was struggling to understand how exactly UMAP is different from tSNE.

He then goes on and attempts to explain exactly why UMAP does so much better than tSNE. None of his explanation mentions category theory.

Since I don’t really understand UMAP or why it does better than tSNE, I can’t add anything to this discussion. In particular, I can’t say how much the category theory really helps. All I can do is explain a bit of the category theory. I’ll do that now, very briefly, just as a way to get a conversation going. I will try to avoid category-theoretic jargon as much as possible—not because I don’t like it or consider it unimportant, but because that jargon is precisely what’s stopping certain people from understanding Section 2.

I think it all starts with this paper by Spivak, which McInnes, Healy and Melville cite but for some reason don’t provide a link to:

• David Spivak, Metric realization of fuzzy simplicial sets.

Spivak showed how to turn a ‘fuzzy simplicial set’ into an ‘uber-metric space’ and vice versa. What are these things?

An ‘uber-metric space’ is very simple. It’s a slight generalization of a metric space that relaxes the usual definition in just two ways: it lets distances be infinite, and it lets distinct points have distance zero from each other. This sort of generalization can be very useful. I could talk about it a lot, but I won’t.

A fuzzy simplicial set is a generalization of a simplicial set.

A simplicial set starts out as a set of vertices (or 0-simplices), a set of edges (or 1-simplices), a set of triangles (or 2-simplices), a set of tetrahedra (or 3-simplices), and so on: in short, a set of n-simplices for each n. But there’s more to it. Most importantly, each n-simplex has a bunch of faces, which are lower-dimensional simplices.

I won’t give the whole definition. To a first approximation you can visualize a simplicial set as being like this:



But of course it doesn’t have to stop at dimension 3—and more subtly, you can have things like two different triangles that have exactly the same edges.

In a ‘fuzzy’ simplicial set, instead of a set of n-simplices for each n, we have a fuzzy set of them. But what’s a fuzzy set?

Fuzzy set theory is good for studying collections where membership is somewhat vaguely defined. Like a set, a fuzzy set has elements, but each element has a ‘degree of membership’ that is a number 0 < x ≤ 1. (If its degree of membership were zero, it wouldn't be an element!)

A map f: X → Y between fuzzy sets is an ordinary function, but obeying this condition: it can only send an element x ∈ X to an element f(x) ∈ Y whose degree of membership is greater than or equal to that of x. In other words, we don't want functions that send things to things with a lower degree of membership.

Why? Well, if I'm quite sure something is a dog, and every dog has a nose, then I'm must be at least equally sure that this dog has a nose! (If you disagree with this, then you can make up some other concept of fuzzy set. There are a number of such concepts, and I'm just describing one.)

So, a fuzzy simplicial set will have a set of n-simplices for each n, with each n-simplex having a degree of membership… but the degree of membership of its faces can't be less than its own degree of membership.

This is not the precise definition of fuzzy simplicial set, because I'm leaving out some distracting nuances. But you can get the precise definition by taking a nuts-and-bolts definition of simplicial set, like Definition 3.2 here:

• Greg Friedman, An elementary illustrated introduction to simplicial sets.

and replacing all the sets by fuzzy sets, and all the maps by maps between fuzzy sets.

If you like visualizing things, you can visualize a fuzzy simplicial set as an ordinary simplicial set, as in the picture above, but where an n-simplex is shaded darker if its degree of membership is higher. An n-simplex can’t be shaded darker than any of its faces.

How can you turn a fuzzy simplicial set into an uber-metric space? And how can you turn an uber-metric space into a fuzzy simplicial set?

Spivak focuses on the first question, because the answer is simpler, and it determines the answer to the second using some category theory. (Psst: adjoint functors!)

The answer to the first question goes like this. Say you have a fuzzy simplicial set. For each n-simplex whose degree of membership equals a, you turn it into a copy of this uber-metric space:

\{ (t_0, t_1, \dots, t_n) : t_0 + \cdots + t_n = - \log a , \; t_0, \ldots, t_n \geq 0 \} \subseteq \mathbb{R}^{n+1}

This is really just an ordinary metric space: an n-simplex that’s a subspace of Euclidean (n+1)-dimensional space with its usual Euclidean distance function. Then you glue together all these uber-metric spaces, one for each simplex in your fuzzy simplical set, to get a big fat uber-metric space.

This process is called ‘realization’. The key here is that if an n-simplex has a high degree of membership, it gets ‘realized’ as a metric space shaped like a small n-simplex. I believe the basic intuition is that an n-simplex with a high degree of membership describes an (n+1)-tuple of things—its vertices—that are close to each other.

In theory, I should try to describe the reverse process that turns an uber-metric space into a fuzzy simplicial set. If I did, I believe we would see that whenever an (n+1)-tuple of things—that is, points of our uber-metric space—are close, they give an n-simplex with a high degree of membership.

If so, then both uber-metric spaces and fuzzy simplicial sets are just ways of talking about which collections of data points are close, and we can translate back and forth between these descriptions.

But I’d need to think about this a bit more to do a good job of going further, and reading the UMAP paper a bit more I’m beginning to suspect that’s not the main thing that practitioners need to understand. I’m beginning to think the most useful thing is to get a feeling for fuzzy simplicial sets! I hope I’ve helped a bit in that direction. They are very simple things. They are also closely connected to an idea from topological data analysis:

• Nina Otter, Magnitude meets persistence. Homology theories for filtered simplicial sets.

I should admit that McInnes, Healy and Melville tweak Spivak’s formalism a bit. They call Spivak’s uber-metric spaces ‘extended-pseudo-metric spaces’, but they focus on a special kind, which they call ‘finite’. Unfortunately, I can’t find where they define this term. They also only consider a special sort of fuzzy simplicial set, which they call ‘bounded’, but I can’t find the definition of this term either! Without knowing these definitions, I can’t comment on how these tweaks change things.