El Premio Nerode EATCS-IPEC es un premio teórico de informática otorgado por investigaciones destacadas en el área de algorítmica multivariada . Es otorgado por 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 en la que formula la hipótesis del tiempo exponencial y la utiliza para determinar la complejidad parametrizada exacta de varias variantes importantes del problema booleano de satisfacibilidad . [3]
- 2014: Hans L. Bodlaender , Rodney G. Downey , Michael R. Fellows , Danny Hermelin, Lance Fortnow y Rahul Santhanam, por su trabajo sobre kernelización , que demuestra que varios problemas con algoritmos manejables de parámetros fijos no tienen núcleos de tamaño polinómico a menos que la jerarquía polinómica 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 de parámetros fijos para dominación y cubre problemas en gráficos. [6]
- 2016: Andreas Björklund por su artículo Sumas determinantes para hamiltonicidad no dirigida , 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 matroide para desarrollar núcleos de tamaño polinomial para problemas relacionados y transversales de ciclo impar . [9] [10]
- 2019: Noga Alon , Raphael Yuster y Uri Zwick , por inventar la técnica de codificación por colores , un ingrediente muy importante 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 que se han convertido en herramientas elegantes y eficientes utilizadas para establecer la manejabilidad de parámetros fijos de los problemas de 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: B. Courcelle por su trabajo sobre la definibilidad de propiedades de grafos en 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]
Ver también
Referencias
- ^ Premio IPEC Nerode, Asociación Europea de Informática Teórica , consultado el 3 de septiembre de 2015.
- ^ "Premio EATCS-IPEC Nerode", Complejidad parametrizada , consultado el 3 de septiembre de 2015.
- ^ Premio EATCS-IPEC Nerode 2013 - Laudatio, Asociación Europea de Informática Teórica , 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 EATCS-IPEC Nerode 2014 - Laudatio, Asociación Europea de Informática Teórica , consultado el 3 de septiembre de 2015.
- ^ Hajiaghayi gana el premio Nerode 2015, Instituto de Estudios Avanzados en Computación de la Universidad de Maryland, 8 de mayo de 2015 , consultado el 3 de septiembre de 2015.
- ^ Premio EATCS-IPEC Nerode 2016, Asociación Europea de Informática Teórica , 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". República del Silicio . Consultado el 1 de noviembre de 2022 .
- ^ "Los profesores de Computación de NUS, Sanjay Jain y Frank Stephan, ganan el premio Nerode de EATCS-IPEC". Computación NUS . 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.
