Computer Laboratory

Project: Parameterizations of Graph Isomorphism

Some years ago, I supervised an MPhil dissertation on the parameterized complexity of the graph isomorphism problem. A copy can be found here. There has been further progress on it since then. For instance you might look at this paper. A number of open questions remain and a good project might survey the area focussing on one of these.

One parameterization that is not mentioned in either of these references that might also be worth looking at is the Weisfeiler-Leman (W-L) dimension. The k-dimensional Weisfeiler-Leman test (for a fixed number k) is an algorithm that runs in time $n^{O(k)}$ and approximates isomorphism. It is an open question whether this can be made fixed-parameter tractable - i.e. whether it can be run in time $f(k)n^c$ for some constant $c$, and arbitrary function $f$. Investigating this might be a project in itself. A relevant recent paper is here.

Project: Linear Programming and Fixed-Point Logic

In work I did with two post-docs a few years ago, we proved that linear programming problems could be expressed in the formalism of fixed-point logic. This can be found in this paper,

In the concluding section of that paper are some open questions. One of them asks whether Linear Programming is FPC-complete under first-order (or similar) reductions. I think this may be a problem that could be tackled within the scope of an MPhil project.

Project:Definability and Machine Learning

There is intriguing work regarding about connections between the expressive power of logics and the formalization of problems in machine learning. Details of this can be found it in the following two papers:

They contain several possible leads to open questions that could form a good basis for a project.

Project:Locality in Finite Structures

This is a project more in the realm of logic. This paper contains interesting explorations regarding the locality properties of first-order logic on finite structures:

There are a number of interesting open questions here that a research project could be based on.

Project: Graph Isomorphism Lower Bounds

The graph isomorphism problem has an intriguing status in complexity theory. It is neither known to be in P nor known to be NP-complete. In particular, very little has been shown regarding its hardness. It is not known to be P-hard. This project would explore the hardness of the problem under strong assumptions (such as the strong exponential time hypothesis). Some papers that might offer a starting point are this one and this one

In addition, the following projects involve a substantial implementation component and could also be suitably adapted for a Part II project.

Project: Emulating Quantum Circuits

This paper describes a way to emulate the evaluation of quantum circuits. It reduces the problem to counting the number of solutions of Boolean formulas in a particular form: There are also recent advances in fast constrained counting and sampling, using hashing and SAT solvers: The project would seek to bring these together to construct a fast emulator for quantum circuits and perform a test run of Shor's factorization algorithm