Премия Мачти

Премия Махти вручается на ежегодном симпозиуме IEEE по основам компьютерных наук (FOCS) авторам лучших студенческих работ. Статья считается студенческой, если на момент подачи все авторы являются студентами дневной формы обучения. Решение о награждении принимает Программный комитет.

Премия названа в честь Майкла Махти, исследователя в области теоретической информатики в 1970-х годах. ^[1] Аналогом этой награды на симпозиуме ACM по теории вычислений (STOC) является премия Дэнни Левина за лучшую студенческую работу . ^[2]

Предыдущие получатели

Предыдущие лауреаты премии Махти указаны в таблице ниже. ^{[ нужна ссылка ]}

Год	Получатель (Университет)	Бумага
2021	Сяо Мао ( Массачусетский технологический институт )	«Преодоление кубического барьера для (невзвешенного) расстояния редактирования дерева»
2020	Рахул Иланго ( Массачусетский технологический институт )	«Формула постоянной глубины и версии MCSP с частичными функциями сложны»
2019	Джейсон Ли ( CMU )	«Быстрый минимальный k-разрез простого графа»
2019	Джош Алман ( Массачусетский технологический институт ) Лицзе Чен ( Массачусетский технологический институт )	«Эффективное построение жестких матриц с использованием NP-оракула»
2018	Шуичи Хирахара ( Токийский университет )	«Сокращение от худшего до среднего случая без черного ящика в пределах NP»
2018	Урмила Махадев ( Калифорнийский университет в Беркли )	«Классическая проверка квантовых вычислений»
2017	Расмус Кинг ( Йельский университет ) Пэн Чжан ( Технологический институт Джорджии )	«Результаты твердости структурированных линейных систем» ^[3]
2016	Майкл Б. Коэн ( Массачусетский технологический институт )	«Графы Рамануджана за полиномиальное время» ^[4]
2016	Авиад Рубинштейн (Беркли)	«Урегулирование сложности расчета приближенного равновесия Нэша для двух игроков» ^[5]
2015	Мика Гёос ( Университет Торонто )	«Нижние границы клики против независимого множества»
2015	Аарон Сидфорд ( Массачусетский технологический институт ) Тат Ли ( Массачусетский технологический институт Инь Сэм Чиу-вай Вонг ( Калифорнийский университет, Беркли )	«Быстрый метод секущей плоскости и его применение для комбинаторной и выпуклой оптимизации»
2014	Аарон Сидфорд (MIT) Инь Тат Ли (MIT)	«Методы поиска пути для линейного программирования: решение линейных программ в итерациях Õ (√rank) и более быстрые алгоритмы для максимального потока»
2013	Джона Шерман ( Калифорнийский университет, Беркли )	«Почти максимальные расходы за почти линейное время» ^[6]
2012	Нир Битански ( Тель-Авивский университет ), Омер Панет ( Бостонский университет )	«От невозможности запутывания к новой методике моделирования без черного ящика»
2011	Каспер Грин Ларсен ( Орхус )	«О поиске диапазона в групповой модели и комбинаторном несоответствии»
2011	Тимон Хертли ( ETH Zurich )	«3-SAT быстрее и проще — уникальные границы SAT для удержания PPSZ в целом»
2010	Аарон Потечин ( Массачусетский технологический институт )	«Границы монотонных коммутационных сетей для направленной связности»
2009	Alexander Sherstov ( UT Austin )	«Пересечение двух полупространств имеет высокую пороговую степень»
2009	Джона Шерман ( Калифорнийский университет, Беркли )	«Преодоление барьера многопродуктового потока для sqrt(log(n))-приближений к самому разреженному разрезу»
2008	Михай Патрашку ( Массачусетский технологический институт )	"Сукцинктер"
2007	Пер Острин ( KTH )	«К резкой неаппроксимируемости для любого 2-CSP»
2006	Николас Дж.А. Харви (MIT)	«Алгебраические структуры и алгоритмы для задач сопоставления и матроидов»
2005	Марк Браверман ( Торонто )	«О сложности вещественных функций»
2005	Тим Эбботт (MIT), Дэниел Кейн (MIT), Пол Валиант (MIT)	«О сложности игр двух игроков «выигрыш-проигрыш»»
2004	Лап Чи Лау (Торонто)	«Приблизительная теорема Макса-Штайнера-упаковки деревьев о минимальном разрезе Штейнера»
2004	Марцин Муха ( Варшава ), Петр Санковски (Варшава)	«Максимальные совпадения посредством исключения по Гауссу»
2003	Subhash Khot ( Princeton )	«Трудность аппроксимации задачи о кратчайшем векторе в нормах с высокими Lp»
2002	Боаз Барак ( Вейцман )	«Постоянное подбрасывание монеты с человеком посередине или реализация модели общей случайной строки»
2002	Харальд Рэке ( «Падерборн »)	«Минимизация перегрузок в общих сетях»
2001	Боаз Барак (Вейцман)	«Как преодолеть барьер симуляции черного ящика»
2001	Vladlen Koltun ( Tel Aviv )	«Почти точные верхние границы для вертикального разложения в четырех измерениях»
2000	Петр Индик ( Стэнфорд )	«Стабильные распределения, генераторы псевдослучайных чисел, встраивания и вычисления потоков данных»
1999	Маркус Блэзер ( Бонн )	"А 5/2 н. ²-Нижняя граница ранга умножения матриц n×n над произвольными полями»
1999	Эрик Вигода ( Беркли )	«Улучшенные границы выборки раскрасок»
1998	Камаль Джайн ( Технологический институт Джорджии )	«Алгоритм аппроксимации коэффициента 2 для обобщенной задачи сети Штейнера»
1998	Дэниел Мичиансио (MIT)	«Задачу о кратчайшем векторе NP-трудно аппроксимировать с точностью до некоторой константы»
1997	Сантош Вемпала ( CMU )	«Алгоритм на основе случайной выборки для изучения пересечения полупространств»
1996	Джон Кляйнберг (MIT)	«Неразделимый поток с одним источником»
1995	Андраш Бенчур (MIT)	«Отображение сокращения периферийного подключения с приложениями в 6/5 раз»
1995	Сатьянараяна В. Локам ( Чикаго )	«Спектральные методы определения жесткости матрицы с применением к компромиссу между размером и глубиной и сложности связи»
1994	Ракеш К. Синха, Т.С. Джейрам ( Вашингтон )	«Эффективные программы ветвления с забвением для пороговых функций»
1994	Джеффри С. Джексон ( CMU )	«Эффективный алгоритм запроса членства для изучения DNF с учетом равномерного распределения»
1993	Паскаль Койран	«Слабая версия модели Blum, Shub & Smale»
1992	Бернд Гертнер ( ФУ Берлина )	«Субэкспоненциальный алгоритм для абстрактных задач оптимизации»
1991	Анна Галь (Чикаго)	«Нижние оценки сложности надежных логических схем с шумными вентилями»
1991	Джайкумар Радхакришнан ( Рутгерс )	«Лучшие оценки для пороговых формул»
1990	Дэвид Цукерман (Беркли)	«Общие слабые случайные источники»
1989	Бонни Бергер (MIT) Джон Ромпель (MIT)	«Моделирование (журнал ^с n )-мудрая независимость в NC"
1988	Шмуэль Сафра (Вейцман)	«О сложности омега-автоматов»
1987	Джон Кэнни (MIT)	«Новый алгебраический метод планирования движения роботов и реальной геометрии»
1987	Абхирам Дж. Ранаде ( Йельский университет )	«Как эмулировать общую память (предварительная версия)»
1986	Прабхакар Рагхаван (Беркли)	«Вероятностное построение детерминированных алгоритмов: аппроксимация целочисленных программ упаковки»
1985	Рави Б. Боппана (MIT)	«Усиление вероятностных булевых формул»
1984	Джоэл Фридман (Гарвард)	«Построение монотонных формул размера O ( n log n ) для k -го элементарного симметричного многочлена от n логических переменных»
1983	Гарри Мейрсон (Стэнфорд)	«Программная сложность поиска по таблице»
1982	Карл Стертивант ( Университет Миннесоты )	«Обобщенные симметрии полиномов алгебраической сложности»
1981	Ф. Томсон Лейтон (MIT)	«Новые методы нижней границы для СБИС»

См. также

Ссылки

^ Список публикаций Майкла Махти в DBLP
^ ACM SIGACT. Премия Дэнни Левина за лучшую студенческую работу. Архивировано 20 июня 2008 года в Wayback Machine.
^ «Награда за лучшую бумагу FOCS 2017» (PDF) .
^ «Награда за лучшую бумагу FOCS 2016» (PDF) .
^ «Награда за лучшую бумагу FOCS 2016» (PDF) .
^ «Награда за лучшую бумагу FOCS 2013» . Архивировано из оригинала 13 декабря 2013 г. Проверено 6 декабря 2013 г.

[1] Список публикаций Майкла Махти в DBLP

[2] ACM SIGACT. Премия Дэнни Левина за лучшую студенческую работу. Архивировано 20 июня 2008 года в Wayback Machine.

[3] «Награда за лучшую бумагу FOCS 2017» (PDF) .

[4] «Награда за лучшую бумагу FOCS 2016» (PDF) .

[5] «Награда за лучшую бумагу FOCS 2016» (PDF) .

[6] «Награда за лучшую бумагу FOCS 2013» . Архивировано из оригинала 13 декабря 2013 г. Проверено 6 декабря 2013 г.

[1]

[2]

[3]

[4]

[5]

[6]