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 Unique Games Conjecture
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
An ACS project in 2020 developed this further and can be found here. The key question that remains open would be the definable version of the unique games conjecture. A project might aim to examine approaches to the classical unique games conjecture and also to improve the soundness/completeness gap achieved in previous work.
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
Project: Semidefinite Programming Lower Bounds
For many NP-hard optimization problems, some of the best approximation algorithms are based on semidefinite programming relaxations. In work I did with my PhD student, Pengming Wang, we showed that lower bounds for many such approximation algorithms could be derived from results on logical definability. Details can be found here. The proposed project would explore this for some new approximation problems, such as graph spanners.
Project: List Graph Isomorphism
While the complexity of graph isomorphism is famously unresolved, a variation known as list graph isomorphism is known to be NP-complete. This paper gives a classification of some cases where list graph isomorphism is tractable and others where it is NP-complete. A natural conjecture arising from this is that the problem is NP-complete in any class where the Weisfeiler-Leman algorithm fails. The project would investigate this possibilty