Премия EATCS –IPEC Nerode — теоретическая премия в области компьютерных наук , присуждаемая за выдающиеся исследования в области многомерной алгоритмики . Она присуждается Европейской ассоциацией теоретической компьютерной науки и Международным симпозиумом по параметризованным и точным вычислениям . [1] Премия была впервые предложена в 2013 году. [2]
Победители
На данный момент победителями стали:
- 2013: Крис Калабро, Рассел Импальяццо , Валентин Кабанец, Рамамохан Патури и Фрэнсис Зейн за исследования, формулирующие гипотезу экспоненциального времени и использующие ее для определения точной параметризованной сложности нескольких важных вариантов проблемы выполнимости булевых уравнений . [3]
- 2014: Ханс Л. Бодлендер , Родни Г. Дауни , Майкл Р. Феллоуз , Дэнни Хермелин, Лэнс Фортноу и Рахул Сантханам за работу по кернелизации , доказавшую, что несколько задач с фиксированными параметрами, поддающимися обработке алгоритмами, не имеют ядер полиномиального размера, если только полиномиальная иерархия не разрушается. [4] [5]
- 2015: Эрик Демейн , Федор В. Фомин , Мохаммад Хаджиагайи и Димитриос Тиликос за исследования двумерности , определяющие широкую основу для разработки алгоритмов с фиксированными параметрами для решения задач доминирования и покрытия на графах. [6]
- 2016: Андреас Бьёрклунд за статью « Определяющие суммы для ненаправленной гамильтоновости» , в которой показано, что методы, основанные на алгебраической теории графов, приводят к значительно улучшенному алгоритму поиска гамильтоновых циклов [7]
- 2017: Федор В. Фомин , Фабрицио Грандони и Дитер Кратч за разработку метода «измеряй и властвуй» для анализа алгоритмов обратного отслеживания. [8]
- 2018: Стефан Кратч и Магнус Вальстрём за работу с использованием теории матроидов для разработки ядер полиномиального размера для задач трансверсали нечетных циклов и связанных с ними задач. [9] [10]
- 2019: Нога Алон , Рафаэль Юстер и Ури Цвик — за изобретение техники цветового кодирования , чрезвычайно важного компонента в наборе инструментов параметризованного проектирования алгоритмов. [11]
- 2020: Дэниел Маркс, Цзянер Чен, Ян Лю, Сунцзянь Лу, Барри О'Салливан, Игорь Разгон — за изобретение концепций важных разделителей и разрезов, которые стали элегантными и эффективными инструментами, используемыми для установления разрешимости задач с фиксированными параметрами графов. [12]
- 2021: CS Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan, за их алгоритм квазиполиномиального времени для решения игр на четность . [13]
- 2022: Бруно Курсель за теорему Курселя о фиксированно-параметрической трактовке свойств графов в монадической логике второго порядка .
- 2023: Марек Цыган, Йеспер Недерлоф, Марчин Пилипчук, Михал Пилипчук, Йохан ММ ван Рой и Якуб Онуфрий Войтащик за статью « Решение проблем связности, параметризованных с помощью ширины дерева, за одно экспоненциальное время » . [14]
- 2024: Ханс Л. Бодлендер, Федор В. Фомин , Дэниел Локштанов, Элко Пеннинкс, Сакет Саураб и Димитриос М. Тиликос за статью (Мета)Кернелизация . [15]
Смотрите также
Ссылки
- ^ Премия IPEC Nerode, Европейская ассоциация теоретической информатики , получено 03.09.2015.
- ^ "EATCS-IPEC Nerode Prize", Параметризованная сложность , получено 2015-09-03.
- ^ Премия EATCS-IPEC Nerode 2013 — Laudatio, Европейская ассоциация теоретической информатики , получено 03.09.2015.
- ^ Нельсон, Патрик (6 октября 2014 г.). «Академик выигрывает международную премию по математике» . Получено 1 ноября 2022 г.
- ^ Премия EATCS-IPEC Nerode 2014 — Laudatio, Европейская ассоциация теоретической информатики , получено 03.09.2015.
- ^ Хаджиагайи выигрывает премию Нерода 2015 года, Институт передовых компьютерных исследований Мэрилендского университета, 8 мая 2015 г. , получено 03.09.2015.
- ^ EATCS-IPEC Nerode Prize 2016, Европейская ассоциация теоретической информатики , 29 августа 2016 г. , получено 29 августа 2016 г..
- ^ АЛГО 2017, АЛГО 2017, 3 сентября 2017 г. , получено 3 сентября 2017 г..
- ^ "Магнус Вальстрём был удостоен премии Нероде 2018 года". 13 мая 2018 г. Архивировано из оригинала 25 января 2022 г. Получено 1 ноября 2022 г.
- ^ Основные докладчики ALGO 2018, Хельсинкский институт информационных технологий , получено 24 августа 2018 г.
- ^ Премия EATCS-IPEC Nerode 2019, Европейская ассоциация теоретической информатики , 3 сентября 2019 г. , получено 01.01.2020.
- ^ Дармоди, Дженни (16.12.2020). «Ирландский профессор Барри О'Салливан получил глобальную премию в области компьютерных наук». Silicon Republic . Получено 01.11.2022 .
- ^ "Профессора вычислительной техники NUS Санджай Джейн и Фрэнк Стефан стали обладателями премии EATCS-IPEC Nerode Prize". NUS Computing . Получено 01.11.2022 .
- ^ Премия EATCS-IPEC Nerode 2023, Европейская ассоциация теоретической информатики , получено 18 января 2024 г..
- ^ Премия EATCS-IPEC Nerode 2024, Европейская ассоциация теоретической информатики , получено 06.09.2024.
