Pebble games, monads and comonads in classical, probabilistic and quantum computation
Pebble games are an important and widely used tool in logic, algorithms and complexity, constraint satisfaction and database
The idea is that we can explore a pair of structures, e.g. graphs, by placing up to k pebbles on them, so we have a window
of size at most k on the two structures. If we can always keep these pebbles in sync so that the two k-sized windows look
the same (are isomorphic) then we say that Duplicator has a winning strategy for the k-pebble game.
This gives a resource-bounded notion of approximation to graphs and other structures which has a wide range of applications.
Monads and comonads are widely used in functional programming, e.g. in Haskell, and come originally from category theory.
It turns out that pebble games, and similar notions of approximate or local views on data, can be captured elegantly by comonads,
and this gives a powerful language for many central notions in constraints, databases and descriptive complexity. For example,
k-consistency can be captured in these terms; another important example is treewidth, a key parameter which is very widely
used to give “islands of tractability” in otherwise hard problems.
Finally, monads can be used to give various notions of approximate or non-classical solutions to computational problems. These
include probabilistic and quantum solutions. For example, there are quantum versions of constraint systems and games which
admit quantum solutions when there are no classical solutions, thus demonstrating a “quantum advantage”. Monads and comonads
can be used in combination, making use of certain “distributive laws”.
The aim of this project is to explore a number of aspects of these ideas. Depending on the interests and background of the
student, different aspects may be emphasised, from functional programming, category theory, logic, algorithms and descriptive
complexity, probabilistic and quantum computation.
Some specific directions include: 1. Developing Haskell code for the k-pebbling comonad and various non-classical monads,
and using this to give a computational tool-box for various constructions in finite model theory and probabilistic or quantum
computation. 2. Developing the category-theoretic ideas involved in combining monads and comonads, and studying some examples.
3. Using the language of comonads to capture other important combinatorial invariants such as tree-depth. 4. Developing the
connections between category theory, finite model theory and descriptive complexity.
Some background reading.
1. Leonid Libkin, Elements of finite model theory. (Background on pebble games and the connection with logic and complexity).
2. The pebbling comonad in finite mode theory. S. Abramsky, A. Dawar and P. Wang. (Technical report describing the basic ideas
which can serve as a starting point.)