Prestigious Nerode Prize for Pioneering Work on Sparsity
Jaroslav Nešetřil and Patrice Ossona de Mendez laid the foundations for a significant area of structural graph theory, known as Sparsity. Their work has not only profoundly influenced pure mathematics but also has practical applications in algorithmic graph theory, computational complexity, and mathematical logic. This year, they were awarded the prestigious Nerode Prize.
Last Wednesday in Warsaw, the prestigious 2025 Nerode Prize was awarded, a testament to an extraordinary contribution to the field of theoretical computer science. The prize, which is awarded annually by the European Association for Theoretical Computer Science (EATCS), was received by professor Jaroslav Nešetřil from the IUUK at Matfyz and professor Patrice Ossona de Mendez both from EHESS Paris and from the IUUK at Matfyz for their pioneering work on „sparsity“ in graph theory. Both scientists personally accepted the award at a ceremony in Poland.
The Nerode Prize is given for exceptional work in the field of multivariate algorithms and is named after the distinguished American mathematician and logician Anil Nerode. It recognizes influential and lasting contributions that have pushed the boundaries of the field. The award is given for a single paper or a series of papers published within the last fifteen years, and its laureates are selected by a committee of leading experts.
This year’s prize was awarded for a fundamental contribution that laid the foundations of Sparsity: an area of structural graph theory that focuses on the concepts of nowhere dense graph classes and graph classes with bounded expansion. These two definitions robustly capture the concept of local, structural sparseness in graphs and finite structures. In their acclaimed series of papers and their monography Sparsity, published by Springer in 2012, Nešetřil and Ossona de Mendez introduced key notions and demonstrated their fundamental character. They succeeded in proving a wide range of properties and equivalent characterizations, thereby creating a powerful toolbox of techniques for working with sparse graphs and structures.
As their previous work has shown, this toolbox can be used to design parameterized algorithms for problems of a local nature. Over the years, this has led to several breakthrough results in parameterized complexity, particularly to major advances in understanding the complexity of problems definable in First-Order logic. The pioneering work of Nešetřil and Ossona de Mendez created an impressive bridge between structural graph theory, logic, model theory and multivariate algorithmics, leaving a lasting mark on all these fields. The work of both scientists was supported by an ERC Synergy Grant from the European Research Council.
