El EATCS - IPEC Nerode Prize es un premio teórico de informática otorgado por una investigación destacada en el área de la algorítmica multivariante . Es otorgado por la Asociación Europea de Ciencias de la Computación Teórica y el Simposio Internacional sobre Computación Parametrizada y Exacta . [1] El premio se ofreció por primera vez en 2013. [2]
Ganadores
Los ganadores del premio hasta ahora han sido:
- 2013: Chris Calabro, Russell Impagliazzo , Valentine Kabanets, Ramamohan Paturi y Francis Zane, por su investigación que formula la hipótesis del tiempo exponencial y la utiliza para determinar la complejidad exacta parametrizada de varias variantes importantes del problema de satisfacibilidad booleano . [3]
- 2014: Hans L. Bodlaender , Rodney G. Downey , Michael R. Fellows , Danny Hermelin, Lance Fortnow y Rahul Santhanam, por su trabajo sobre kernelización , demostrando que varios problemas con algoritmos manejables de parámetros fijos no tienen núcleos de tamaño polinomial a menos que la jerarquía del polinomio colapse. [4]
- 2015: Erik Demaine , Fedor V. Fomin , Mohammad Hajiaghayi y Dimitrios Thilikos, por su investigación sobre bidimensionalidad , definiendo un marco amplio para el diseño de algoritmos de dominación de parámetros fijos y tratables y cubriendo problemas en gráficos. [5]
- 2016: Andreas Björklund por su artículo Determinant Sums for Undirected Hamiltonicity , que muestra que los métodos basados en la teoría de grafos algebraicos conducen a un algoritmo significativamente mejorado para encontrar ciclos hamiltonianos [6]
- 2017: Fedor V. Fomin , Fabrizio Grandoni y Dieter Kratsch, por desarrollar el método "medir y conquistar" para el análisis de algoritmos de retroceso. [7]
- 2018: Stefan Kratsch y Magnus Wahlström por su trabajo utilizando la teoría matroide para desarrollar núcleos de tamaño polinomial para problemas transversales de ciclo impar y problemas relacionados. [8]
- 2019: Noga Alon , Raphael Yuster y Uri Zwick , por inventar la técnica de codificación de colores , un ingrediente muy importante en la caja de herramientas del diseño de algoritmos parametrizados. [9]
Ver también
Referencias
- ^ Premio IPEC Nerode , Asociación europea de informática teórica , consultado el 3 de septiembre de 2015.
- ^ "EATCS-IPEC Nerode Prize" , Parameterized Complexity , consultado el 3 de septiembre de 2015.
- ^ EATCS-IPEC Nerode Prize 2013 - Laudatio , European Association for Theoretical Computer Science , consultado el 3 de septiembre de 2015.
- ^ EATCS-IPEC Nerode Prize 2014 - Laudatio , European Association for Theoretical Computer Science , consultado el 3 de septiembre de 2015.
- ^ Hajiaghayi gana el Premio 2015 Nerode , Universidad de Maryland Instituto de Altos Estudios de Informática 8 de mayo de 2015 , recuperada 03/09/2015.
- ^ EATCS-IPEC Nerode Prize 2016 , European Association for Theoretical Computer Science , 29 de agosto de 2016 , consultado el 29 de agosto de 2016.
- ^ ALGO 2017 , 2017 ALGO 3 de septiembre de 2017 , recuperada 03/09/2017.
- ^ Oradores principales de ALGO 2018 , Instituto de Tecnología de la Información de Helsinki , consultado el 24 de agosto de 2018
- ^ EATCS-IPEC Nerode Prize 2019 , European Association for Theoretical Computer Science , 3 de septiembre de 2019 , consultado el 1 de enero de 2020..