![[TopOx] Jakub Opršal: Homotopy theory in the complexity of homomorphism problems @ToposInstitute](https://i.ytimg.com/vi/fU2pZbrE2aA/maxresdefault.jpg)
Uploaded January 2026 | Updated September 2026, 2 weeks ago
27th of November 2025. Slides available at https://topos.institute/events/topox/
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.
27th of November 2025. Slides available at https://topos.institute/events/topox/
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.
![[TopOx] Jakub Opršal: Homotopy theory in the complexity of homomorphism problems](https://i.ytimg.com/vi/fU2pZbrE2aA/mqdefault.jpg "[TopOx] Jakub Opršal: Homotopy theory in the complexity of homomorphism problems
27th of November 2025. Slides available at https://topos.institute/events/topox/
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.")
![[Oxford Seminar] Khyathi Komalan | Adult Brainrot: Mandela Effect, Misinformation & Conspiracies](https://i.ytimg.com/vi/gk0jJtjNQGI/mqdefault.jpg "[Oxford Seminar] Khyathi Komalan | Adult Brainrot: Mandela Effect, Misinformation & Conspiracies
Oxford Seminar, 25th of September 2025
Abstract: The internet is a strange place — one moment youre
convinced the Starbucks logo never had a star on top, the next youre
knee-deep in a rumor that spreads everywhere at once, and before long
youre staring at a series of pictures that prove the moon landing
was fake. These phenomena may look like pure nonsense, but they also
show how perception, memory, and belief are shaped by our
experiences, the hidden biases behind what we perceive, and the
difficulty of stitching multiple pieces of information, sometimes
conflicting, into a coherent story that fits the most into ones
worldview.
In this talk I introduce adult brainrot as a categorical framework
for these inconsistencies. I will show how categorical models of
quantum processes can capture order-sensitive memory and
indistinguishable sources of misinformation, and how categorical
notions of centers help explain why people’s theories sometimes fail
to form a consistent picture of reality. The aim is to argue that
quantum categorical structures offer a natural mathematical framework
for modeling the inconsistencies and oddities of human perception and
belief.")
![[2-torial] Quantum information theory, Part 4: Quantum bird watching (continued)](https://i.ytimg.com/vi/gl2Ni8ksGsc/mqdefault.jpg "[2-torial] Quantum information theory, Part 4: Quantum bird watching (continued)
2-torial, May 20 2026
You can find accompanying notes and other information on this video at https://topos.institute/work/lectures/2-torials/2026-05-20_hosgood_quantum/
Tutor: Tim Hosgood
Tutee: Jason Brown
The elements of quantum information theory are not so complicated: some linear algebra over the complex numbers and a bit of classical probability theory. But it doesnt take long before you run into some intriguing problems that showcase how established experimental results contradict our classical intuition. In this 2-torial we will learn the very basics of quantum theory, see how a Mach–Zehnder interferometer gives a real-world implementation of a classically impossible construction and suggests that we should go all in on complex numbers, and finally how this all applies to the world of theoretical bird watching via the Quantum Zeno effect.")
![[Oxford Seminar] José Siqueira | Double functorial representation of indexed monoidal structures](https://i.ytimg.com/vi/glQUcRImOkw/mqdefault.jpg "[Oxford Seminar] José Siqueira | Double functorial representation of indexed monoidal structures
Oxford Seminar, 12th of June 2025
The data of a logical doctrine acts in two directions: that of the *substitution* operation, and that of *quantification*. Double Category Theory provides the tools to capture these two actions and their relationship concomitantly: in a double category of spans, re-indexing and acting on predicates can be packaged as tight and loose arrows respectively, and in there tight arrows always have conjoints. By mapping these conjoints into a double category of quintets, we obtain adjunctions internal to a 2-category. Moreover, by using the notion of adequate triple, the indexing category need only have certain pullbacks.
Adding a monoidal structure to the fibers (and the double pseudofunctor) allows us to capture both the Beck-Chevalley and Frobenius conditions. We will concern ourselves with the monoidal analogues of regular hyperdoctrines and similar structures (where the objects of predicates are not necessarily posets, but rather live in some 2-category), and show how they are equivalent to (lax symmetric monoidal) double pseudofunctors between spans and quintet double categories.")
![[DOTS Lectures] 4. Composing Moore Machines](https://i.ytimg.com/vi/jsM2jTuT_Zc/mqdefault.jpg "[DOTS Lectures] 4. Composing Moore Machines
Part of a lecture series on the Double Operadic Theory of Systems (DOTS) presented by David Jaz Myers.")
![[2-torial] David Jaz tells Brendan about a topos-theoretic interpretation for conceptual modelling](https://i.ytimg.com/vi/kFQpKp-ehZI/mqdefault.jpg "[2-torial] David Jaz tells Brendan about a topos-theoretic interpretation for conceptual modelling
Recorded at the Oxford Office on the 5th of December 2025.")
