Department of Computer Science and Technology

The following contains ideas which might form the starting point of a project for Part III or ACS. These are quite open-ended descriptions. They often revolve around an open question, but it is not expected that a question like this could be resolved in the space of a single project. Rather, the question should serve as motivation for exploring the research area and the literature around it.

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: 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: Factoring and Graph Isomorphism

Integer factoring and graph isomorphism are two classic computational decision problems which are neither known to be polynomial-time solvable nor known to be NP-complete. They are classed as potentially "NP-intermediate". At the same time, no formal relationship between them has been established. Neither is known to be reducible to the other. For a closely related factoring problem, that of factoring univariate polynomials, algorithms are known which seem to use an isomorphism test (or an approximation thereof) as a black box. See for instance this paper. This project will aim to extract from this and related work a possible reduction between the problems.

• © 2023 Department of Computer Science and Technology, University of Cambridge