How Complex is Category Theory?

Peter Hines

This talk is about the computational difficulty of working with structures from the foundations of category theory -- and indeed, whether doing so is of any interest to practical computer scientists.

Category theory is commonly and affectionately called 'abstract nonsense', even by its practitioners. A perceived advantage of categorical reasoning is that it provides a beautiful high-level language that allows us to unify concepts across a number of fields -- recent deep connections between Quantum Mechanics and Linguistics being a prime example.

By contrast, the claim that category theory provides concrete tools that may be used to solve practical problems is less widespread!

This talk aims to demonstrate by example that this is indeed the case. It presents some fundamental topics from the foundations of category theory from this point of view. The claim is that the theory of categorical coherence has something non-trivial to say about the complexity of certain real-world computational tasks.

Very little prior knowledge of category theory is assumed!

This talk is an expanded version of a talk given at Category Theory 2014.