skip to content

Department of Computer Science and Technology

For his work in – quite literally – trying to prove the impossible, Professor Anuj Dawar has been awarded a European Research Council (ERC) Advanced Grant.

The grant to Anuj, Professor of Logic and Algorithms here, will fund five years of research aimed at helping develop mathematical proofs that for certain types of notoriously complex problems, no efficient way exists to solve them through computation.

"Some problems are inherently difficult to solve computationally. We've known about them for decades without coming up with efficient algorithms to solve them," Anuj says. "We don't think it's because no-one has found such an algorithm yet, but rather because there simply aren't any efficient algorithms. But the challenge lies in demonstrating that: it’s very hard to prove that something doesn't exist."

For me, a key driver is wanting to further our fundamental, conceptual understanding of the nature of computation and what’s possible – and what’s impossible – within it.

One notoriously hard problem of the kind he’s interested in is the 'travelling salesman' question. In this mathematical problem, a notional salesperson is given a set of places to visit within a certain time. The challenge is to compute the most optimal route for travelling to them all. Work is still going on (including by Anuj's colleagues here Amanda Prorok and Ben Hudson) to try and develop a truly efficient solution for this.

Anuj would argue that the reason why the search for the most efficient solution is still continuing is that there isn't one. And if that could be proved, he says, it would stop people wasting their time looking for an answer that doesn’t exist.

It would have other advantages as well. "The study of computational complexity theory has educated generations of computer scientists to think about this complexity, to recognise hard problems and to develop ingenious work-arounds," he says.

The 'travelling salesman' problem falls into a class of problems famously known as the P versus NP problem. This asks whether every problem whose solution can be quickly verified can also be quickly solved.

The problem, first formulated about half a century ago, has generated a large amount of research in computational complexity – but as yet, has got us no closer to directly solving it.

"One reason why," explains Anuj, "is that there is currently no credible path of steps that could be taken that would lead us to resolving the question. It has become obvious that a solution will require the development of major new theoretical tools – but at the moment, it’s not even clear what such tools might consist of."

This is the starting point for his proposed work on his ERC project, which is titled The Limits of Symmetric Computation.

Symmetric algorithms
From previous research he’s carried out in the field, Anuj thinks he has found a way to approach the issue. "While we don't know how to prove impossibility for all algorithms," he explains, "if we restrict the kinds of algorithms we consider, there are certain types where we can prove impossibility – symmetric algorithms."

These tend to be the kind of algorithms that come into play when a high-level description is automatically translated into a computational task – like the algorithms that go to work when, for example, we type a query into a database and it is translated into the process of searching the data.

"The algorithms that have these kinds of symmetries generally can't solve certain kinds of problems," he says. "So in this project we'll be addressing the challenge of expanding the mathematical notion of symmetry to cover a broader range of algorithms. And that will help us identify exactly which kind of problems these algorithms aren't able to solve."

To help with this classification work, he also wants to bring in newer mathematical methods that haven’t so far been used in computer science. So he’ll be looking to recruit postdoctoral researchers and PhD students with skills in the areas of algebraic topology, category theory, permutation group theory and representation.

The ERC funding will enable him to recruit these researchers. We congratulate Anuj on obtaining it. ERC Advanced Grants are designed to support excellent scientists and scholars who are already established research leaders and have a track record of research achievements. The grants carry significant prestige, with researchers competing at the highest level internationally to obtain them. This year, more than 1,700 researchers applied but only 253 were successful.

'A fascinating puzzle'
The grant funding will help Anuj develop his studies of the symmetry of computation and advance our insights into the nature of computation. "For me, a key driver is wanting to further our fundamental, conceptual understanding of the nature of computation and what’s possible – and what’s impossible – within it," he says.

"It’s a fascinating puzzle."

Published by Rachel Gardner on Tuesday 26th April 2022