Resources in Computation

Pebble games have been shown to be a powerful method for proving complexity lower bounds for symmetric circuits. This has been established in the case of Boolean circuits and algebraic circuits. In the case of algebraic circuits, some lower bounds have been proved using variations of the pebble game that do not have a strong connection with model connection games. In this talk, I will review the background of the connection between pebble games and circuit lower bounds, discuss the general form of pebble games. Time permitting, I will explain some new results characterising symmetric algebraic circuits.

The cohomological k-consistency algorithm is a polynomial time algorithm for CSP that provides a simple and surprisingly powerful connection between local constraint propagation and Abramsky and Brandenburger's sheaf theoretic approach to contextuality. This algorithm appears to unite several "islands of tractability" in CSP theory and it remains open whether it suffices to solve all efficiently solvable CSPs. This short talk will provide an overview of the algorithm, the recent progress towards establishing bounds on its computational power and future work on extending this connection between topology, contextuality and classical computation.

This talk will go over recent results in my joint work with Anuj Dawar on Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras (pBAs). There it was shown that the satisfiability problem for the class of non-trivial pBAs is NP-complete. For the class of pBAs which arise in quantum theory, the problem is undecidable. However, if the dimension of quantum system is fixed and greater than 3 (if complex) or 2 (if real), then we showed that the satisfiability problem is complete for the existential theory of the reals. Interestingly, the proof of these results use witnesses to contextuality, e.g. Kochen-Specker sets and Peres-Mermin magic square, as gadgets. I will conclude the talk by explaining ongoing work relating these results to the complexity of the quantum homomorphism and isomorphism problem in bounded dimension. Relevant paper: https://arxiv.org/abs/2602.24164.

This work-in-progress talk investigates no-go results for quantum realizations of correlations in the sheaf-theoretic framework. By viewing quantum realizations with POVMs and PVMs as compatible families over presheaves, we formulate a sheaf-theoretic analogue of recent no-go theorems by Kunjwal and V.K [2025]. We then apply this viewpoint to develop preliminary results toward state-independent logical contextuality.

We generalize the Abramsky--Brandenburger sheaf-theoretic framework for contextuality by replacing probability distributions with distributions valued in a convex effect algebra A. This yields a notion of A-valued measurement model encompassing probabilistic, deterministic, and quantum measurement structures within a single framework. States sigma: A -> [0,1] induce ordinary empirical models, allowing observable behaviour to be viewed as arising from effect-valued measurement data. This leads to a distinction between internal contextuality of A-models and observable contextuality after state evaluation. We analyze the relationship between these notions and identify coherence conditions under which observable classical explanations assemble into internal ones. Using the ordered-vector-space representation of effect modules, we show that non-contextuality is characterized by feasibility of an associated cone program, generalizing the linear-programming formulation of contextuality in the probabilistic case. We also introduce an effect-valued contextual fraction and study its relation to observable contextuality witnesses. We analyze sharp realizability and uniform dilation for measurement models, clarifying the relationship between general POVMs and projective measurements. We also show how resource-indexed effect algebras induce graded monads, generalizing the quantum monad.

Large vision–language models, such as OpenAI's CLIP, excel at image–text alignment but neglect the compositional structure of their underlying data. We introduce two new tools DisCoCLIP and QuCLIP, multimodal encoders that combines transformer architectures with tensor network encoders. We explicitly encode the logical structure of data into a type categorial grammar for text and tree tensor networks for images. Trained end-to-end with a self-supervised contrastive loss both on tensors and variational quantum circuits, our models raise CLIP’s accuracies by 4% to 10% on existing benchmarks, and by 40% on our own novel benchmark. More importantly, the models rely on a fraction of the parameters used by CLIP, reduced from 64M to between 10K to 100K.

We provide a categorical treatment of Canetti's Universal Composability (UC) framework for systems with a static number of parties and sessions. This yields three benefits: First, we present our results graphically yet retain their rigor by using string diagrams. Second, categories let us generalize so that our results do not apply only to interactive Turing machines but also to other forms of computation, such as quantum or domain-specific languages. Third, categories help us to drop some unnecessary restrictions of UC (e.g., our adversary can be a computational network rather than a single Turing machine); we prove equivalence between our variant and the usual UC, showing no expressiveness is lost.

In this talk we survey recent results on the power of linear and semidefinite programming hierarchies for the Graph Isomorphism problem, obtained via an interplay of methods from algebraic graph theory, finite model theory, and the theory of C*-algebras. We also discuss progress towards further applications of the methods, as well as possible probabilistic and quantum interpretations.

In this talk I will survey a categorical perspective on the algebraic approach to the (P)CSP. In particular we discuss how many of standard constructions in the CSP world can be equivalently described as well-known and well-studied categorical notions, such as Kan extensions, Grothendieck construction, nerve-realisation (akin to the constructions in algebraic topology), etc.

Lattices may be viewed as certain adjunctions between distributive lattices. In this setting, Whitman’s Theorem about free lattices, which is closely related to games, may be viewed as a stepwise construction of the free lattice by duality in the tradition of Ghilardi and Abramsky.

Samson Abramsky. A Cook's Tour of the Finitary Non-Well-Founded Sets. We Will Show Them! Essays in honor of Doc Gabbay (1) 2005. College Publications, pp. 1-18 Mai Gehrke and Elena Pozzan. On the choice of topological dual of a lattice. To appear in volume in honor of H. A. Priestley. https://hal.science/hal-05567267v1/document Silvio Ghilardi. An algebraic theory of normal forms. Ann. Pure Appl. Logic (1995) 71:189-245. André Joyal. Free Lattices, Communication and Money Games, in Logic and Scientific Methods: Volume One of the Tenth International Congress of Logic, Methodology and Philosophy of Science, Florence, August 1995. Springer Netherlands 1997, pp. 29-68. Philip M. Whitman. Free Lattices, Annals of Mathematics Vol. 42, No. 1 (Jan., 1941), pp. 325-330.

In 2020 (revised 2022) Ji, Natarajan, Vidick, Wright, and Yuen proved MIP* = RE by encoding instances of the Halting problem as nonlocal games whose entangled-player value is 1 if the encoded machine halts and ≤ 1/2 otherwise. The construction uses a compression procedure that lets a verifier, via quantum self‑testing, offload sampling and verification complexity to entangled provers. This leads to the complexity-theoretic conclusion that the class of languages decidable by multi-prover interactive proofs with entangled provers (MIP*) equals the recursively enumerable languages (RE), and the physical consequence that Tsirelson’s problem has a negative answer: the set of correlations achievable by commuting-operator strategies strictly contains those achievable by tensor-product strategies.

The game comonad programme revealed a deep connection between model comparison games, morphisms, and logic fragments for relational structures. Extending this connection beyond relational signatures, and systematically addressing resources, has remained largely unexplored. We present two complementary approaches. The first develops a resource-parametric coalgebraic game framework in a general category, in which classical comparison games arise as instances and new ones become available by varying the resources that shape the game. We then provide an algorithmic method to solve all such games. The second constructs a comonad over arbitrary categories and comprehensively characterises resource constraints along traces.

The quantum constraint satisfaction problem is a non-classical analogue of the standard CSP, motivated by questions in quantum information theory, in particular on the role of entanglement in computational and communication tasks. In this talk, based on joint work with Gideo Joubert and Antoine Mottet, I will present an algebraic framework for reductions between quantum CSPs based on the notion of quantum polymorphisms. This framework characterises exactly which classical CSP reductions lift to the quantum setting via the commutativity gadgets introduced by Zhengfeng Ji. Hence, it provides a systematic method for applying the algebraic CSP machinery to understand the complexity of deciding whether a nonlocal game admits a winning quantum strategy. Applications include complexity classifications for quantum CSPs parameterised by odd cycles, Siggers clauses, and all Boolean languages. The starting points of all reductions are quantum XOR (shown undecidable by William Slofstra) and quantum 3SAT (shown undecidable as a consequence of the MIP*=RE theorem).

This work in progress talk will look at a natural extension of the resource parameters for game comonads, and their connection to logic.

Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting. We show that if an adaptive ℤ₂-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively. (Joint work with Samson Abramsky, Carmen Constantin, and Martti Karvonen).

In this work-in progress talk we will study contextual games, a generalisation of non-local games to arbitrary measurement scenarios. Implicit in the work of Abrasmky et al on the quantum monad is a contextual CSP game which provides a direct operational interpretation of quantum homomorphisms: perfect state-independent quantum strategies correspond precisely to Kleisli morphisms for the quantum monad. We extend this correspondence to a a state-dependent version of the quantum monad. That is, we show that Kleisli morphisms for this variant of the quantum monad capture state-dependent perfect strategies in the contextual CSP game. This extends the quantum monad framework beyond state-independent contextuality and naturally captures examples such as the GHZ game.

Dependence logic was introduce with the book "Dependence Logic" (CUP 2007). Dependence logic has three equivalent semantics: (1) Tarski style team semantics, (2) game-theoretic semantics played with teams, and (3) game-theoretic semantics played with elements. We can think of semantics also in terms of the differences between models rather than what is true in the models. The Ehrenfeucht-Fraisse-game for first order logic as well as other logics is a method for investigating differences between two models. There is the "team" version of the Ehrenfeucht-Fraisse-game, equivalent to elementary equivalence for types (1) and (2) semantics (2007). As a new game we present an "element" version of the Ehrenfeucht-Fraisse-game for dependence logic. Moves are elements, not teams. To account for dependence, players make commitments. We consider an example and show that the new game characterizes elementary equivalence in dependence logic. This is joint work with Joni Puljujärvi.

Discrete-variable photonic quantum computing offers strong potential for scalable quantum technologies. In particular, the boson sampling task, which can natively be implemented on photonic platforms, has already led to several demonstrations of quantum advantage. However, photonic quantum computing also face important challenges, notably the probabilistic nature of two-qubit gates in passive linear optics.

We develop the EF game comonad construction for continuous first-order logic (CFO), which is a many-valued extension of classical first-order logic used to express properties of metric structures.

The talk will start by introducing state-independent contextuality, as illustrated by the well-known Peres-Mermin magic square. This will give the motivation for introducing commutation groups in order to obtain a purely algebraic characterisation of state-independent contextuality. I will discuss how commutation groups can be presented by generators and relations and their connection to a directed version of the Heisenberg group. The main point of this construction is that it allows one to identify contextuality witnesses in the form of contextual words and I will give an overview of the settings in which such contextual words can arise. I will end by mentioning the unitary representations of commutation groups as subgroups of generalised Pauli n-groups.

Quantum nonlocality paradoxes, such as that of GHZ, provide maximally sharp logical obstructions to classical probabilistic models of quantum correlations. They are key resources in a broad variety of information-theoretic tasks that exhibit unconditional quantum advantage. For example, in nonlocal games, which are communication tasks that serve as core technical tools in recent landmark results in quantum computational complexity theory. Abramsky et al. (2017) exhibited a novel family of three-qubit strong nonlocality paradoxes in which Charlie can perform one of two measurements and Alice and Bob's outcomes satisfy a linear system conditioned on his outcome. In this work, we completely classify all such biconditioned parity proofs, by introducing new structural and combinatorial techniques. We find that the landscape of nonlocality paradoxes is far richer than previously understood, violating regularity conditions underlying all prior constructions.

Initial algebras, such as the algebras of natural numbers, binary strings, and trees, form the backbone of any structural approach to mathematics. They provide a formalization of the “algebra of all freely generated elements for a given signature,” which serves as the syntax of that signature. Unfortunately, by definition, all initial algebras support a form of primitive recursion. As a result, defining functions over them can easily lead to computational explosion, making these algebras ill-suited to capturing low-complexity computation in a structural way. In this talk, inspired by Leivant’s work on predicativism, we introduce a universal notion called an Eide object, formalizing the idea of the “set of all blueprints or ideal forms” (Eide, in Platonic philosophy) for constructing elements from a given signature. Eide objects generalize initial algebras while also providing a complexity-sensitive notion of syntax through which one can capture low-complexity forms of computation. To illustrate this, we focus on word algebras with only constants and unary functions, and show that representability via an Eide object for the corresponding signature characterizes polynomial-time computability in the multi-letter case and linear-space computability in the unary case.