EATCS-IPEC Nerode Prize 2026

The EATCS-IPEC Nerode Prize for outstanding papers in the area of multivariate algorithmics is awarded to

Bingkai Lin

for his paper

  • "The Parameterized Complexity of the k-Biclique Problem", Journal of the ACM 65(5):1-23, 2018.

Laudatio:

The Nerode Prize 2026 is awarded for the proof that the Biclique problem is W[1]-complete, and therefore does not admit an FPT algorithm unless FPT=W[1]. In the Biclique problem input is a graph G and integer k, and the task is to determine whether G contains as a subgraph a complete bipartite graph with k vertices on both sides. Despite the apparent similarity to the classic Clique problem, the parameterized complexity of Biclique remained a prominent open problem in parameterized algorithms until its resolution by the Nerode Award paper.

Furthermore, the hardness proof of Biclique established the hardness of parameterized approximation of the maximum set intersection problem. The hardness of maximum set intersection was subsequently used as a starting point to show hardness of parameterized approximation of Dominating Set, Even Set and the Shortest Vector problem, each of which were hailed as landmark results in parameterized complexity. Thus the hardness proof for the Biclique problem not only resolved a long standing open problem, it also served as a first building block in the emerging theory of parameterized inapproximability. For this reason the Nerode Prize 2026 Committee unanimously decided that the paper by Lin deserves to win the Nerode Prize.

Nerode Prize Committee: Sang-il Oum (chair), Russell Impagliazzo, Michał Pilipczuk

 

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.