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