Лэнс Фортноу
Лэнс Фортноу | |
|---|---|
| Рожденный | 15 августа 1963 г. лет ) ( 60 |
| Национальность | Американский |
| Альма-матер | Корнелльский университет Массачусетский технологический институт |
| Известный | Интерактивные доказательства |
| Награды | Член ACM , NSF член президентского факультета , стипендиат Фулбрайта , премия Нероде |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Иллинойский технологический институт Технологический институт Джорджии Северо-Западный университет Чикагский университет |
| Докторантура | Майкл Сипсер |
| Докторанты | Карстен Лунд |
| Веб-сайт | http://lance.fortnow.com/ http://blog.computationalcomplexity.org/ |
Лэнс Джереми Фортноу (родился 15 августа 1963 г.) — ученый-компьютерщик, известный своими крупными результатами в области вычислительной сложности и интерактивных систем доказательства . Он является деканом вычислительного колледжа Иллинойского технологического института .
Биография [ править ]
Лэнс Фортноу получил докторскую степень по прикладной математике в Массачусетском технологическом институте в 1989 году. [1] под руководством Майкла Сипсера . После окончания учебы он работал на факультете Чикагского университета (1989–1999, 2003–2007), Северо-Западного университета (2008–2012) и Технологического института Джорджии (2012–2019) в качестве заведующего Школой компьютерных наук . . [2] [3]
Фортноу был главным редактором-основателем журнала ACM Transactions on Computation Theory в 2009 году. [4] Он был председателем ACM SIGACT. [5] и его сменил Пол Бим. Он был председателем конференции IEEE по сложности вычислений. [6] с 2000 по 2006 год. В 2002 году он начал один из первых блогов, посвященных теоретической информатике. [7] и с тех пор пишет для этого. С 2007 года у него есть со-блогер Уильям Гасарч . статью, в которой описывается прогресс, достигнутый в решении проблемы P и NP В сентябре 2009 года Фортнов привлек внимание общественности к теории сложности, опубликовав в журнале Communications of the Computing Machinery . [8]
Работа [ править ]
В своих многочисленных публикациях Фортнов внес важные результаты в область сложности вычислений . Еще будучи аспирантом Массачусетского технологического института, Фортнов показал, что не существует идеальных протоколов с нулевым разглашением для NP-полных языков, если только полиномиальная иерархия не рухнет. [9] Вместе с Майклом Сипсером он также продемонстрировал, что относительно конкретного оракула существует язык в co-NP , не имеющий интерактивного протокола. [10]
В ноябре 1989 года Fortnow получил электронное письмо от Ноама Нисана , в котором говорилось, что у со-NP есть несколько интерактивных доказательств (MIP). Вместе с Карстеном Лундом и Говардом Карлоффом он использовал этот результат для разработки алгебраической техники построения интерактивных систем доказательства и доказательства того, что каждый язык в иерархии с полиномиальным временем имеет интерактивную систему доказательства. [11] Их работе не исполнилось и двух недель, как Ади Шамир использовал ее, чтобы доказать, что IP = PSPACE . [12] Быстро развив это (17 января 1990 г., менее чем через два месяца после получения электронного письма от Нисана), Фортнов вместе с Ласло Бабаем и Карстеном Лундом доказал, что MIP = NEXP . [13] Эти алгебраические методы были расширены Фортновом, Бабаем, Леонидом Левиным и Марио Сегеди , когда они представили новый общий механизм проверки вычислений. [14]
Fortnow продолжает публиковать публикации по различным темам в области вычислительной сложности, включая дерандомизацию , разреженные языки и машины-оракулы . Fortnow также опубликовал публикации по квантовым вычислениям , теории игр , секвенированию генома и экономике .
Работа Фортнау в области экономики включает работу в области теории игр, оптимальных стратегий и прогнозирования. Вместе с герцогом Вангом он исследовал классическую задачу теории игр о дилемме заключенного , расширив ее так, что дилемма ставится последовательно бесконечное число раз. Они исследовали, какие стратегии следует использовать игрокам, учитывая ограничения, заключающиеся в том, что они черпают свои стратегии из вычислительно ограниченных множеств и вводят «периоды отсрочки», чтобы предотвратить доминирование мстительных стратегий. [15] Fortnow также изучил правило логарифмического рыночного скоринга (LMSR) вместе с маркет-мейкерами . Он помог показать, что ценообразование LMSR является #P-жестким , и предложил метод аппроксимации для ценообразования на рынках перестановок. [16] Он также внес свой вклад в исследование поведения информированных трейдеров, работающих с маркет-мейкерами LMSR. [17]
Фортнов также написал научно-популярную книгу « Золотой билет: P, NP и поиск невозможного» . [18] который был во многом основан на статье, которую он написал для CACM в 2009 году. [19] В своей книге Фортнов представляет нетехническое введение в проблему P и NP и ее алгоритмические ограничения. Далее он описывает свою книгу и иллюстрирует, почему проблемы NP так важны, в подкасте Data Skeptic . [20]
Награды и почести [ править ]
- 2007 г. Сотрудник ACM
- Сотрудник президентского факультета NSF с 1992 по 1998 год.
- Стипендиат Фулбрайта в Нидерландах в 1996 и 1997 годах.
- 2014 г. Премия Нероде
Ссылки [ править ]
- ^ Лэнс Фортноу в проекте «Математическая генеалогия»
- ^ «Колледж вычислительной техники нанимает Фортнау Антона руководителем школы» (пресс-релиз). Технологический колледж вычислительной техники Джорджии . 19 марта 2012 года . Проверено 4 октября 2012 г.
- ^ Факультет кафедры электротехники и информатики Северо-Западного университета
- ^ Транзакции ACM по теории вычислений
- ^ ACM СИГАКТ
- ^ Конференция IEEE по вычислительной сложности
- ^ Блог о сложности вычислений
- ^ Дж. Маркофф, «Помимо призов, головоломка P-NP имеет последствия», The New York Times , 7 октября 2009 г. (требуется подписка)
- Л. Фортнау, «Состояние проблемы P и NP» , Сообщения ACM 9 (2009). - ^ Л. Фортнов, «Сложность совершенного нулевого знания» в С. Микали, редакторе, «Случайность и вычисления» , том 5 « Достижения в области компьютерных исследований» , страницы 327-343. JAI Press, Гринвич, 1989 г.
- ^ Л. Фортноу и М. Сипсер, «Существуют ли интерактивные протоколы для языков co-NP?» , Письма об обработке информации , 28:249-251, 1988 г.
- ^ К. Лунд, Л. Фортноу, Х. Карлофф и Н. Нисан, «Алгебраические методы для интерактивных систем доказательства» , Журнал ACM , 39 (4): 859-868, 1992.
- ^ А. Шамир, «IP = PSPACE» , Журнал ACM 39 (4): 869-877, 1992.
- ^ Л. Бабай, Л. Фортнов и К. Лунд, «Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя доказательствами» , Computational Complexity , 1 (1): 3-40, 1991
- ^ Л. Бабай, Л. Фортнов, Л. Левин и М. Сегеди. «Проверка вычислений в полилогарифмическом времени» , в Трудах 23-го симпозиума ACM по теории вычислений , страницы 21–31. ACM, Нью-Йорк, 1991 г.
- ^ Л. Фортноу и Д. Ванг, «Оптимальность и доминирование в повторяющихся играх с ограниченными игроками» , в Трудах 26-го симпозиума ACM по теории вычислений , страницы 741-749. ACM, Нью-Йорк, 1994 г.
- ^ Ю. Чен, Л. Фортноу, Н. Ламберт, Д. Пеннок и Дж. Вортман, «Сложность комбинаторных маркет-мейкеров» , в материалах 9-й конференции ACM по электронной коммерции , страницы 190-199. ACM, Нью-Йорк, 2008 г.
- ^ Ю. Чен, С. Димитров, Р. Сами, Д. Ривз, Д. Пеннок, Р. Хэнсон, Л. Фортноу и Р. Гонен, «Рынки игровых прогнозов: равновесные стратегии с маркет-мейкером», Algorithmica , 2009 г.
- ^ Фортнау, Лэнс Золотой билет: P, NP и поиск невозможного ., Princeton University Press, 2013.
- ^ Фортнау, Лэнс, «Статус проблемы P и NP» , обзорная статья в Communications of the ACM , 52 (9): 78-86, сентябрь 2009 г.
- ^ «P против NP» , Скептик данных , 2017 г.
