Image: © sergign/Stock.adobe.com
The director of the Insight SFI Research Centre for Data Analytics is the first Irish recipient of the Nerode Prize.
As part of the International Symposium on Algorithms and Computation (ISAAC) this week, Prof Barry O’Sullivan was announced as the winner of one of the top computer science prizes in the world.
The Nerode Prize is awarded for outstanding research in the area of multivariate algorithmics by the European Association for Theoretical Computer Science and the International Symposium on Parameterized and Exact Computation.
O’Sullivan, who is a professor at University College Cork and director of the Insight SFI Research Centre for Data Analytics, won for his paper which resolved one of the most famous open problems in the fields of complexity theory.
The directed feedback vertex set problem, which is addressed by O’Sullivan and his co-authors, arises in many practical applications if someone wants to remove cycles in a directed graph, for example, in deadlock recovery in databases, circuit testing, operating systems and in social networks.
Another interesting application arises in networks that model the transmission of diseases such as Covid-19.
This marks the first time the Nerode Prize has been awarded to an Irish recipient. O’Sullivan, who spoke at Future Human earlier this year, said he is “delighted to be a recipient of the award” for work published in the Journal of the ACM.
Barry O’Sullivan. Image: Colm Mahady/Fennell Photography
He explained that while finding a solution to some problems 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,” he said.
This year’s award committee comprised Hans Bodlaender of Utrecht University, Virginia Williams of MIT and Anuj Dawar of Cambridge University.
In a statement, the Nerode Prize committee said the paper won the award “based on its excellent technical exposition and its introduction of a seminal technique that has led to many key research directions in parameterised complexity”.
