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: Definable Inapproximability

In a joint paper with Albert Atserias, I explored lower bounds on the approximability of some NP-complete problems, using notions of definability in logic. The paper can be found here

The theory developed there could be applied to other approximation problems. A particularly interesting one is Max-2SAT. See this paper for more on the classical theory of inapproximability.

Project: Quantum and Classical Complexity Classes

The complexity class that corresponds to quanum polynomial time, BQP is known to be in between the classical complexity classes BPP and AWPP. Details about this can be found in the following paper and references therein.
Fenner: PP-lowness and a simple definition of AWPP

The essential idea is that AWPP can be seen as extending BPP with polynomial scaling, and BQP can be simulated by quadratic scaling. The project would investigate the hierarchy formed inside AWPP by varying the polynomials and see what other extensions of quantum computing can be simulated.

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