El premio Nerode de la EATCS-IPEC es un premio de informática teórica que se otorga a la investigación destacada en el área de algorítmica multivariante . Lo otorga la Asociación Europea de Informática 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 premiados hasta el momento han sido:
- 2013: Chris Calabro, Russell Impagliazzo , Valentine Kabanets, Ramamohan Paturi y Francis Zane, por su investigación que formuló la hipótesis del tiempo exponencial y la utilizó para determinar la complejidad parametrizada exacta 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 la kernelización , que demuestra que varios problemas con algoritmos manejables con parámetros fijos no tienen núcleos de tamaño polinomial a menos que la jerarquía polinomial colapse. [4] [5]
- 2015: Erik Demaine , Fedor V. Fomin , Mohammad Hajiaghayi y Dimitrios Thilikos, por su investigación sobre bidimensionalidad , que define un marco amplio para el diseño de algoritmos manejables con parámetros fijos para problemas de dominación y cobertura en gráficos. [6]
- 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 [7]
- 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. [8]
- 2018: Stefan Kratsch y Magnus Wahlström por su trabajo utilizando la teoría de matroides para desarrollar núcleos de tamaño polinomial para problemas transversales de ciclo impar y relacionados. [9] [10]
- 2019: Noga Alon , Raphael Yuster y Uri Zwick , por inventar la técnica de codificación de colores , un ingrediente de enorme importancia en la caja de herramientas del diseño de algoritmos parametrizados. [11]
- 2020: Daniel Marx, Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, Igor Razgon, por inventar los conceptos de separadores y cortes importantes que se han convertido en herramientas elegantes y eficientes utilizadas para establecer la manejabilidad de parámetros fijos de problemas gráficos. [12]
- 2021: CS Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, por su algoritmo de tiempo cuasipolinomial para decidir juegos de paridad . [13]
- 2022: Bruno Courcelle para el teorema de Courcelle sobre la manejabilidad de parámetros fijos de las propiedades de grafos en la lógica monádica de segundo orden .
- 2023: Marek Cygan, Jesper Nederlof, Marcin Pilipczuk, Michal Pilipczuk, Johan MM van Rooij y Jakub Onufry Wojtaszczyk por su artículo Resolución de problemas de conectividad parametrizados por ancho de árbol en tiempo exponencial único . [14]
- 2024: Hans L. Bodlaender, Fedor V. Fomin , Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh y Dimitrios M. Thilikos por su artículo (Meta)kernelización . [15]
Véase también
Referencias
- ^ Premio IPEC Nerode, Asociación Europea de Ciencias Informáticas Teóricas , consultado el 3 de septiembre de 2015.
- ^ "Premio Nerode EATCS-IPEC", Complejidad parametrizada , consultado el 3 de septiembre de 2015.
- ^ Premio Nerode EATCS-IPEC 2013 - Laudatio, Asociación Europea de Ciencias Informáticas Teóricas , consultado el 3 de septiembre de 2015.
- ^ Nelson, Patrick (6 de octubre de 2014). «Académico gana premio internacional de matemáticas» . Consultado el 1 de noviembre de 2022 .
- ^ Premio Nerode EATCS-IPEC 2014 - Laudatio, Asociación Europea de Ciencias Informáticas Teóricas , consultado el 3 de septiembre de 2015.
- ^ Hajiaghayi gana el premio Nerode 2015, Instituto de Estudios Informáticos Avanzados de la Universidad de Maryland, 8 de mayo de 2015 , consultado el 3 de septiembre de 2015.
- ^ Premio Nerode EATCS-IPEC 2016, Asociación Europea de Ciencias Informáticas Teóricas , 29 de agosto de 2016 , consultado el 29 de agosto de 2016.
- ^ ALGO 2017, ALGO 2017, 3 de septiembre de 2017 , consultado el 3 de septiembre de 2017.
- ^ "Magnus Wahlström recibió el premio Nerode 2018". 13 de mayo de 2018. Archivado desde el original el 25 de enero de 2022. Consultado el 1 de noviembre de 2022 .
- ^ Oradores principales de ALGO 2018, Instituto de Tecnología de la Información de Helsinki , consultado el 24 de agosto de 2018
- ^ Premio EATCS-IPEC Nerode 2019, Asociación Europea de Informática Teórica , 3 de septiembre de 2019 , consultado el 1 de enero de 2020.
- ^ Darmody, Jenny (16 de diciembre de 2020). «El profesor irlandés Barry O'Sullivan gana el premio mundial de informática». Silicon Republic . Consultado el 1 de noviembre de 2022 .
- ^ "Los profesores de informática de la NUS Sanjay Jain y Frank Stephan ganan el premio Nerode de EATCS-IPEC". NUS Computing . Consultado el 1 de noviembre de 2022 .
- ^ Premio EATCS-IPEC Nerode 2023, Asociación Europea de Informática Teórica , consultado el 18 de enero de 2024.
- ^ Premio EATCS-IPEC Nerode 2024, Asociación Europea de Ciencias Informáticas Teóricas , consultado el 6 de septiembre de 2024.
