Undergraduate and Postgraduate Student Projects at QMUL

This page is intended for students at the School for Electrical Engineering and Computer Science at Queen Mary University of London who are considering to write their Undergraduate or Postgraduate Project Thesis in the academic year 2025/2026 with me.

Depending on your skills and interests, projects will generally focus on either implementation and experimentation, or on research in form of mathematical problem solving, but there might of course be an overlap between both types. It is recommended that you took and enjoyed some of the following modules:

ECS407U - Logic and Discrete Structures
ECS421U - Automata and Formal Languages
ECS529U - Algorithms and Data Structures
ECS651U - Computability, Complexity and Algorithms
ECS7018U - Logic in Computer Science

Below are examples of past or ongoing thesis projects, giving a general flavour of projects in my area of computer science. This page will be expanded with available projects for the academic year 2025/2026 in the coming weeks.

All projects are/were scalable to either an UG or a PG project and the expectations and goals will be/have been set accordingly. You are also very welcome to approach me with an individual suggestion of a project. Feel free to contact me if you would like to learn more about one or more of these projects and my research, or if you would like to chat about your own project ideas.

Past / Ongoing Projects

Counting 3-matchings in subcubic time

Type: Implementation and Experimentation

A 3-matching in a graph is a set of three edges that do not share common endpoints:

Three examples of a 3-matching and one non-example of a 3-matching. Note that the rightmost picture is a non-example since the two orange-brown edges share a common vertex.

Given a large graph (think of a social network), the number of 3-matchings reveals information about its clustering behaviour. A naive algorithm for counting all 3-matchings in a graph takes cubic time; given a network with millions or billions of nodes, this is infeasible, even with modern hardware. Recent progress in the area of parameterised algorithmics implies the existence of a quite intricate algorithm for counting 3-matchings with subcubic running time that relies on fast matrix multiplication. The goal of this project is thus the implementation of this algorithm and an evaluation of its performance on (large) benchmark instances.

CFI Graphs: Generation and Experimentation

Type: Implementation and Experimentation

CFI Graphs (named after Cai, Führer, and Immermann) are mathematical tools for the investigation of the expressiveness of Graph Neural Networks and heuristics for comparing large networks. Concretely, CFI Graphs always come in pairs where one graph is obtained by "twisting" the other; below is an example:

A pair of CFI graphs. The right graph is obtained from the left graph by "twisting" the green edges.

A function f from graphs to natural numbers distinguishes a pair of CFI graphs G and H if f(G) ≠ f(H). For example, the function that counts triangles distinguishes the two graphs above since the left graph contains two triangles, but the right graph does not contain a triangle. It is known that (Message-Passing) Graph Neural Networks "MPGNNs" are unable to compute functions that distinguish CFI graphs. Hence, even the relatively small example given by the two graphs above already implies the quite powerful result that MPGNNs cannot count triangles.

The first goal of this project is the implementation of a system that generates CFI graphs specified by various input parameters. The second goal is then the evaluation of a series of functions and graph parameters on CFI graphs generated in the first goal with the aim of enhancing our understanding of the expressivity of MPGNNs.

Counting k-cycles in restricted graphs

Type: Research and Mathematical Problem Solving

A k-cycle in a graph is a sequence of k pairwise distinct vertices v1,v2,...,vk such that for all i ∈ {1,...,k-1} the vertices vi and vi+1, as well as vk and v1, are connected by an edge. See the example below for the illustration of some 5-cycles in a graph.

A large graph with three highlighted 5-cycles. Note that there are more than just the three highlighted ones.

In this project, we are interested in the computational complexity of counting k-cycles in a graph G. In less formal terms, this means that we either want to find a (theoretically) fast algorithm that counts k-cycles in an input graph, or that we want to prove that no such algorithm can exist under assumptions from complexity theory such as "P ≠ NP".

Unfortunately, it has been known for about 20 years that there is no fast algorithm for counting k-cycles in arbitrary graphs G. For this project, we will therefore restrict the problem to special graphs G (the description of these special graphs is out of the scope of this project description but you are welcome to contact me if you are interested in this project and if you would like to learn more).

Concretely, the goals of this project are twofold:

The (theoretical) development of fast algorithms for counting k-cycles in restricted graphs, or
The construction of rigorous mathematical proofs that no such algorithms exist under assumptions from complexity theory such as "P ≠ NP".

Google Sites

Report abuse