Insight’s Professor Barry O’Sullivan has been named as the first ever Irish recipient of the Nerode Prize.

The Nerode Prize is one of the top prizes in computer science, awarded jointly by IPEC and the European Association for Theoretical Computer Science. The award recognises outstanding papers in the area of multivariate algorithmics. This year’s award committee comprised of Hans Bodlaender (Utrecht), Virgi Williams (MIT) and Anuj Dawar (Cambridge).

The award was announced this week, as part of the 31st International Symposium on Algorithms and Computation (ISAAC) and the 15th International Symposium on Parameterized and Exact Computation (IPEC) which are taking place in Hong Kong.

O’Sullivan said, “I’m delighted to be a recipient of the award this year for work, published some time ago in the Journal of the ACM, that closed the most famous open problem in the field of parameterised complexity.”

O’Sullivan explains, “The most famous problem in computer science is the famous “P vs NP” problem. This is one of the six open Millennium Prize Problems. Informally, the core question is whether for all problems for which the solution can be _checked_ quickly that there is also exists an algorithm that can _find_ the solution quickly. The challenge with some important problems is that the amount of time taken to find solutions grows extremely quickly as the size of the problem grows — exponentially, in fact. However, some problems have been shown that while finding a solution is theoretically hard, it can often be “not too difficult” in practice. This is the field of parameterised complexity theory: while a solution might be very hard to find, properties of those problems can make it easier to find them in practice.”

In this prize-winning paper, O’Sullivan and his co-authors, resolved one of the most famous open-problems in the fields of complexity theory: the infamous Directed Feedback Vertex Set Problem. This is a problem that arises in lots of practical applications where one wants to remove cycles in a directed graph. For example, it arises in deadlock recovery in databases, circuit testing, operating systems, and in social networks. A particularly interesting application arises in networks modelling the transmission of diseases such as COVID19.

Very few papers from Irish scientists have been published in the Journal of the ACM. There has never previously been an Irish recipient of the Nerode Prize.

You can read the about official announcement here.