TopOx
A public-facing seminar run (sporadically) in partnership with the Oxford Mathematics and Computer Science departments, and held in-person in Oxford. We invite speakers for both technical and community-engagement talks related to Category Theory, Logic, Type Theory, Computer Science, and other related disciplines.
Next talk
The talk will be held on Thursday, November the 27th, at 4pm, at the Computer Science Department (Bill Roscoe Lecture Theatre, Room 112), University of Oxford.
Homotopy theory in the complexity of homomorphism problems
I will talk about an emerging connection between homotopy theory and computational complexity of discrete problems. I will outline a theorem stating that contractibility is necessary for tractability (assumin P ≠ NP) in the realm of finite-template constraint satisfaction problems (CSPs).
There are many ways the CSP can be formulated. One of them is as a homomorphism problem: given two relational structures A and B, decide whether there is a homomorphism from A to B. We usually study a restricted version of this problem where B is fixed, e.g., if B is the k-clique graph K_k, the problem is the same as k-colouring of a given graph A. If B is finite (and of finite signature), such a problem is called finite-template. Famously, finite-template CSPs exhibit a P vs NP-complete dichotomy as proved independently by Bulatov and Zhuk in 2017.
The main theorem of the talk states a sufficient condition for NP-completeness in terms of the topology of ‘solution spaces’ and provides both all necessary hardness for the Bulatov–Zhuk dichotomy and also a new proof of an earlier Hell–Nešetřil dichotomy of graph homomorphism problems.
Previous talks
We fully intend for all talks to be recorded and publicly uploaded, but unfortunately technical problems have meant that we have been unable to do so for our first two talks.
Testing artificial mathematical intelligence
Emily Riehl, 1st of July 2025
As Thurston describes in his famous essay “On proof and progress in mathematics,” the answer to the question “What is it that mathematicians accomplish?” is multifaceted. Inspired by Turing’s “Computing machinery and intelligence,” we propose a series of tests to help identify whether a generative AI system can meaningfully contribute to the process of doing mathematics.
Remarks on local state classifiers
Peter Johnstone, 13th of May 2025
In a recent paper, Ryuya Hora introduced a remarkable new concept called a local state classifier, and showed that (when it exists) it provides a solution to Lawvere’s problem of parametrizing the hyperconnected quotients of a given topos by structures internal to the topos. However, he left some questions unanswered. This talk will describe Hora’s construction , together with my attempts to answer the outstanding questions, and some new examples.