Премия Махти
Премия Machtey Award присуждается на ежегодном симпозиуме IEEE по основам компьютерной науки (FOCS) автору(ам) лучшей студенческой работы(й). Работа считается студенческой, если все авторы являются студентами очной формы обучения на дату подачи. Решение о присуждении принимается Программным комитетом.
Премия названа в честь Майкла Махти, исследователя в области теоретической информатики в 1970-х годах. [1] Аналогом этой награды на симпозиуме ACM по теории вычислений (STOC) является премия Дэнни Левина за лучшую студенческую работу . [2]
Прошлые получатели
Ниже приведена таблица прошлых лауреатов премии Махти. [ необходима ссылка ]
| Год | Получатель (Университет) | Бумага |
|---|---|---|
| 2023 | Рахул Иланго ( MIT ) | «SAT сводит проблему к минимальному размеру схемы с помощью случайного оракула» |
| 2022 | Роберт Эндрюс ( UIUC ) | «О матричном умножении и проверке полиномиальной идентичности» [3] |
| 2021 | Сяо Мао ( Массачусетский технологический институт ) | «Преодоление кубического барьера для (невзвешенного) расстояния редактирования дерева» |
| 2020 | Рахул Иланго ( MIT ) | «Формула постоянной глубины и версии частичной функции MCSP сложны» |
| 2019 | Джейсон Ли ( CMU ) | «Более быстрый минимальный k-разрез простого графа» |
| Джош Алман ( Массачусетский технологический институт ) Лиджи Чен ( Массачусетский технологический институт ) | «Эффективное построение жестких матриц с использованием NP Oracle» | |
| 2018 | Шуичи Хирахара ( Токийский университет ) | «Сокращение худшего случая до среднего без применения метода черного ящика в рамках NP» |
| Урмила Махадев ( Калифорнийский университет в Беркли ) | «Классическая проверка квантовых вычислений» | |
| 2017 | Расмус Кинг ( Йель ) Пэн Чжан ( Технологический институт Джорджии ) | «Результаты испытаний на твердость для структурированных линейных систем» [4] |
| 2016 | Майкл Б. Коэн ( Массачусетский технологический институт ) | «Графы Рамануджана за полиномиальное время» [5] |
| Авиад Рубинштейн (Беркли) | «Урегулирование сложности вычисления приближенных равновесий Нэша для двух игроков» [6] | |
| 2015 | Мика Гёос ( Университет Торонто ) | «Нижние границы для клики против независимого множества» |
| Аарон Сидфорд ( Массачусетский технологический институт ) Инь Тат Ли ( Массачусетский технологический институт ) Сэм Чиу-вай Вонг ( Калифорнийский университет, Беркли ) | «Более быстрый метод секущей плоскости и его применение в комбинаторной и выпуклой оптимизации» | |
| 2014 | Аарон Сидфорд (MIT) Инь Тат Ли (MIT) | «Методы поиска пути для линейного программирования: решение линейных программ за Õ(√rank) итераций и более быстрые алгоритмы для максимального потока» |
| 2013 | Джона Шерман ( Калифорнийский университет в Беркли ) | «Почти максимальные потоки за почти линейное время» [7] |
| 2012 | Нир Битанский ( Тель-Авивский университет ), Омер Панет ( Бостонский университет ) | «От невозможности запутывания к новой технике моделирования, отличной от черного ящика» |
| 2011 | Каспер Грин Ларсен ( Орхус ) | «О поиске в диапазоне в групповой модели и комбинаторном несоответствии» |
| Тимон Хертли ( ETH Zurich ) | «3-SAT быстрее и проще — уникальные границы SAT для PPSZ Hold в целом» | |
| 2010 | Аарон Потехин ( MIT ) | «Границы монотонных коммутационных сетей для направленного соединения» |
| 2009 | Александр Шерстов ( Юта Остин ) | «Пересечение двух полупространств имеет высокую пороговую степень» |
| Джона Шерман ( Калифорнийский университет в Беркли ) | «Преодоление барьера многопродуктового потока для sqrt(log(n))-приближений к разреженному сечению» | |
| 2008 | Михай Пэтрашку ( MIT ) | "Сукцинктер" |
| 2007 | Пер Аустрин ( KTH ) | «К резкой неприближенности для любого 2-CSP» |
| 2006 | Николас Дж. А. Харви (MIT) | «Алгебраические структуры и алгоритмы для задач сопоставления и матроидов» |
| 2005 | Марк Брейверман ( Торонто ) | «О сложности действительных функций» |
| Тим Эбботт (MIT), Дэниел Кейн (MIT), | «О сложности игр с двумя игроками, в которых один выигрывает, а другой проигрывает» | |
| 2004 | Лап Чи Лау (Торонто) | «Приблизительная теорема о Макс-Штайнере-дереве-упаковке и Мин-Штайнере-разрезе» |
| Марцин Муха ( Варшава ), Пётр Санковский (Варшава) | «Максимальное совпадение с помощью метода исключения Гаусса» | |
| 2003 | Субхаш Хот ( Принстон ) | «Трудность аппроксимации задачи о кратчайшем векторе в высоких нормах Lp» |
| 2002 | Боаз Барак ( Вейцман ) | «Постоянное подбрасывание монеты с человеком посередине или реализация модели общей случайной строки» |
| Харальд Ракке ( Падерборн ) | «Минимизация перегрузки в сетях общего пользования» | |
| 2001 | Боаз Барак (Вейцман) | «Как преодолеть барьер моделирования черного ящика» |
| Владлен Колтун ( Тель-Авив ) | «Почти точные верхние границы для вертикальных разложений в четырех измерениях» | |
| 2000 | Пётр Индик ( Стэнфорд ) | «Стабильные распределения, псевдослучайные генераторы, вложения и вычисления потоков данных» |
| 1999 | Маркус Блезер ( Бонн ) | «5/2 n 2 -нижняя граница ранга умножения матриц n×n над произвольными полями» |
| Эрик Вигода ( Беркли ) | «Улучшенные границы для выборочных раскрасок» | |
| 1998 | Камал Джайн ( Технологический институт Джорджии ) | «Алгоритм аппроксимации фактора 2 для обобщенной задачи сети Штейнера» |
| Даниэле Мичианчо (MIT) | «Задачу о кратчайшем векторе NP-трудно аппроксимировать с точностью до некоторой константы» | |
| 1997 | Сантош Вемпала ( CMU ) | «Алгоритм на основе случайной выборки для изучения пересечения полупространств» |
| 1996 | Джон Клейнберг (MIT) | «Единый неразделимый поток» |
| 1995 | Андраш Бенчур (MIT) | «Представление сокращений в 6/5 раз пограничного подключения к приложениям» |
| Сатьянараяна В. Локам ( Чикаго ) | «Спектральные методы для определения жесткости матрицы с применением к компромиссам между размером и глубиной и сложности связи» | |
| 1994 | Ракеш К. Синха, ТС Джейрам ( Вашингтон ) | «Эффективные забывающие программы ветвления для пороговых функций» |
| Джеффри С. Джексон ( CMU ) | «Эффективный алгоритм запроса членства для обучения DNF с учетом равномерного распределения» | |
| 1993 | Паскаль Койран | «Слабая версия модели Блюма, Шуба и Смейла» |
| 1992 | Бернд Гертнер ( Свободный университет Берлина ) | «Субэкспоненциальный алгоритм для абстрактных задач оптимизации» |
| 1991 | Анна Галь (Чикаго) | «Нижние оценки сложности надежных булевых схем с шумными вентилями» |
| Джайкумар Радхакришнан ( Рутгерс ) | «Лучшие границы для пороговых формул» | |
| 1990 | Дэвид Цукерман (Беркли) | «Общие слабые случайные источники» |
| 1989 | Бонни Бергер (MIT) Джон Ромпель (MIT) | «Моделирование независимости по (log c n ) в NC» |
| 1988 | Шмуэль Сафра (Вейцман) | «О сложности омега-автоматов» |
| 1987 | Джон Кэнни (MIT) | «Новый алгебраический метод планирования движения робота и реальная геометрия» |
| Абхирам Г. Ранаде ( Йельский университет ) | «Как эмулировать общую память (предварительная версия)» | |
| 1986 | Прабхакар Рагхаван (Беркли) | «Вероятностное построение детерминированных алгоритмов: аппроксимация целочисленных программ упаковки» |
| 1985 | Рави Б. Боппана (MIT) | «Усиление вероятностных булевых формул» |
| 1984 | Джоэл Фридман (Гарвард) | «Построение монотонных формул размера O( n log n ) для k -го элементарного симметрического многочлена n булевых переменных» |
| 1983 | Гарри Мейрсон (Стэнфорд) | «Программная сложность поиска в таблице» |
| 1982 | Карл Стертивант ( Университет Миннесоты ) | «Обобщенные симметрии многочленов в алгебраической сложности» |
| 1981 | Ф. Томсон Лейтон (MIT) | «Новые методы нижних границ для СБИС» |
Смотрите также
Ссылки
- ^ Список публикаций Майкла Махти в DBLP
- ^ ACM SIGACT. "Danny Lewin Best Student Paper Award" Архивировано 20 июня 2008 г. на Wayback Machine
- ^ «Премия FOCS 2022 за лучшую статью».
- ^ «Премии FOCS 2017 за лучшую статью» (PDF) .
- ^ «Премии FOCS 2016 за лучшую статью» (PDF) .
- ^ «Премии FOCS 2016 за лучшую статью» (PDF) .
- ^ "FOCS 2013 Best Paper Awards". Архивировано из оригинала 2013-12-13 . Получено 2013-12-06 .
