News and Views
Prestigious Nerode Prize awarded to UCC academic
UCC’s Prof Barry O’Sullivan has won the 2020 Nerode Prize, one of the top prizes in computer science jointly awarded by the European Association for Theoretical Computer Science (EATCS) and the International Symposium on Parameterized and Exact Computation (IPEC). Prof. O’Sullivan holds the Chair of Constraint Programming in the School of Computer Science & IT at UCC.
The award was announced at the 31st International Symposium on Algorithms and Computation (ISAAC) and the 15th IPEC which took place in Hong Kong from 14-16 Dec 2020.
Being the first Irish recipient of the award, Prof 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.”
Prof O’Sullivan said the most famous problem in computer science is the famous “P vs NP” problem. This is one of the six open Millennium Prize Problems.
In the winning paper, Prof O’Sullivan and his co-authors addressed the core question of whether for all problems for which the solution can be _checked_ quickly that there 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.
The authors solved the core question by positioning that some problems have been shown that while finding a solution is theoretically hard, it can often be “not too difficult” in practice. With the selected approach, the 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 instance, it arises in deadlock recovery in databases, circuit testing, operating systems, and social networks. A particularly interesting application arises in networks modelling the transmission of diseases such as COVID19.
“Based on its excellent technical exposition and its introduction of a seminal technique that has led to many key research directions in parameterized complexity, the Nerode Prize Committee unanimously voted that these foundational papers by … O’Sullivan, B. … be awarded the 2020 Nerode Prize,” written the Award announcement (hyperlink https://eatcs.org/index.php/component/content/article/1-news/2861-eatcs-ipec-nerode-prize-2020-).
The EATCS-IPEC Nerode Prize for outstanding papers in multivariate algorithmics is presented annually with the presentation taking place at IPEC (International Symposium on Parameterized and Exact Computation). A selection committee of prominent CS academics chooses the best papers based on the yearly submissions.
This year’s award selection committee was Hans Bodlaender (Utrecht), Virgi Williams (MIT) and Anuj Dawar (Cambridge).
The Prize, launched in 2013, is named in honour of Anil Nerode in recognition of his major contributions to mathematical logic, the theory of automata, computability and complexity theory.