The EATCS–IPEC Nerode Prize is a

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the

European Association for Theoretical Computer Science The European Association for Theoretical Computer Science (EATCS) is an international organization with a European focus, founded in 1972. Its aim is to facilitate the exchange of ideas and results among theoretical computer scientists as well as ...

and the International Symposium on Parameterized and Exact Computation. The prize was offered for the first time in 2013..

Winners

The prize winners so far have been: *2013: Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi, and Francis Zane, for their research formulating the

exponential time hypothesis In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by . It states that satisfiability of 3-CNF Boolean formulas cannot be solved more quickly than exponential t ...

and using it to determine the exact parameterized complexity of several important variants of the

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

. *2014: Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin,

Lance Fortnow Lance Jeremy Fortnow (born August 15, 1963) is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology. Biogra ...

, and Rahul Santhanam, for their work on

kernelization In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solvi ...

, proving that several problems with fixed-parameter tractable algorithms do not have polynomial-size kernels unless the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...

collapses. *2015:

Erik Demaine Erik D. Demaine (born February 28, 1981) is a professor of computer science at the Massachusetts Institute of Technology and a former child prodigy. Early life and education Demaine was born in Halifax, Nova Scotia, to artist sculptor Martin ...

, Fedor V. Fomin,

Mohammad Hajiaghayi , birth_date = , birth_place = , death_place = , nationality = , fields = Computer science , workplaces = University of Maryland, College Park , alma_mater = Massachusetts Institute of Technology (PhD) ...

, and Dimitrios Thilikos, for their research on

bidimensionality Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounde ...

, defining a broad framework for the design of fixed-parameter-tractable algorithms for domination and covering problems on graphs. * 2016: Andreas Björklund for his paper ''Determinant Sums for Undirected Hamiltonicity'', showing that methods based on

algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph t ...

lead to a significantly improved algorithm for finding Hamiltonian cycles *2017: Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch, for developing the "measure and conquer" method for the analysis of backtracking algorithms. *2018: Stefan Kratsch and Magnus Wahlström for their work using

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

theory to develop polynomial-size kernels for

odd cycle transversal In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a biparti ...

and related problems. *2019:

Noga Alon Noga Alon ( he, נוגה אלון; born 17 February 1956) is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of ...

, Raphael Yuster, and

Uri Zwick Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the ...

, for inventing the

Color-coding In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length in a given graph. The traditional c ...

technique, a vastly important ingredient in the toolbox of parameterized algorithm design. *2020: D. Marx, J. Chen, Y. Liu, S. Lu, B. O’Sullivan, I. Razgon, for inventing the concepts of separators and cuts which have become elegant and efficient tools used to establish the fixed parameter tractability of graph problems. *2021: C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, for their quasipolynomial time algorithm for deciding

parity games A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...

. *2022: B. Courcelle for his work on the definability of graph properties in

monadic second-order logic In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's t ...

References

Theoretical computer science Computer science awards {{sci-award-stub

Winners

See also

References