#### 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