深夜亚洲福利久久

UCC Professor Barry O鈥橲ullivan Wins top CS Nerode Prize

18 Dec 2020

UCC鈥檚 Prof Barry O鈥橲ullivan 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鈥橲ullivan 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鈥橲ullivan said: 鈥淚鈥檓 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鈥橲ullivan said the most famous problem in computer science is the famous 鈥淧 vs NP鈥� problem. This is one of the six open Millennium Prize Problems. 

In the winning paper, Prof O鈥橲ullivan 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 鈥渘ot 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. 

鈥淏ased 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鈥橲ullivan, B. 鈥� be awarded the 2020 Nerode Prize,鈥� written the Award announcement  

 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鈥檚 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.