Computer Laboratory

Project

Parameterizations of Graph Isomorphism

Brief Description:

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

Brief Description:

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

Brief Description:

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:
http://arxiv.org/abs/1701.05487
http://arxiv.org/abs/1708.08081

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

Project

Locality in Finite Structures

Brief Description:

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

Brief Description:

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