Лэнс Фортноу - Lance Fortnow - Wikipedia

Лэнс Фортноу
Родившийся15 августа 1963 г. (1963-08-15) (возраст57)
НациональностьАмериканец
Альма-матерКорнелл Университет
Массачусетский Институт Технологий
ИзвестенИнтерактивные доказательства
НаградыЧлен ACM, NSF Научный сотрудник президентского факультета, Ученый Фулбрайта, Приз Нероде
Научная карьера
ПоляИнформатика
УчрежденияИллинойсский технологический институт
Технологический институт Джорджии
Северо-Западный университет
Чикагский университет
ДокторантМайкл Сипсер
ДокторантыКарстен Лунд
Интернет сайтhttp://lance.fortnow.com/
http://blog.computationalcomplexity.org/

Лэнс Джереми Фортноу (родился 15 августа 1963 г.) специалист в области информатики известен значительными результатами в вычислительная сложность и интерактивные системы доказательства. В настоящее время он является деканом Научного колледжа Иллинойсский технологический институт.

биография

Лэнс Фортноу получил докторскую степень по прикладной математике в Массачусетском технологическом институте в 1989 году.[1] под руководством Майкл Сипсер. С момента окончания учится на факультете Чикагский университет (1989-1999, 2003-2007), Северо-Западный университет (2008-2012), и совсем недавно Технологический институт Джорджии (2012 – настоящее время) в качестве председателя Школа компьютерных наук.[2][3]

Фортноу был главным редактором журнала ACM Transactions on Computing Theory.[4] Он был председателем ACM SIGACT.[5] и его преемником стал Пол Бим. Он был председателем конференции IEEE по вычислительной сложности.[6] с 2000 по 2006 год. В 2003 году Fortnow начал один из первых блогов, посвященных теоретической информатике.[7] и с тех пор пишет для него; с 2007 года у него есть со-блогер, Уильям Гасарх. В сентябре 2009 года Фортноу привлек внимание общественности к теории сложности, когда он опубликовал статью, в которой анализировался прогресс, достигнутый в P против проблемы NP в Коммуникациях Ассоциации вычислительной техники.[8][9]

Работа

В своих многочисленных публикациях Фортноу внес важные результаты в область вычислительная сложность. Еще будучи аспирантом Массачусетского технологического института, Фортноу показал, что не существует идеального нулевого знания. протоколы за НП-полный языков, если только полиномиальная иерархия рушится.[10] Вместе с Майклом Сипсером он также продемонстрировал, что по отношению к конкретному оракулу существует язык в со-НП у которого нет интерактивного протокола.[11]

В ноябре 1989 года Fortnow получил электронное письмо от Ноам Нисан показывая, что co-NP имеет несколько интерактивных доказательств (MIP). С Карстен Лунд и Говарда Карлоффа, он использовал этот результат для разработки алгебраической техники для построения интерактивных систем доказательства и доказательства того, что каждый язык в иерархии полиномиального времени имеет интерактивную систему доказательства.[12] Их работе едва исполнилось две недели, когда Ади Шамир использовал это, чтобы доказать, что IP =PSPACE.[13] Вскоре после этого (17 января 1990 г., менее чем через два месяца после получения электронного письма Нисана) Фортноу вместе с Ласло Бабай и Карстен Лунд доказали, что MIP =NEXP.[14] Эти алгебраические методы были расширены Фортноу, Бабаем, Леонид Левин, и Марио Сегеди когда они представили новый общий механизм для проверки вычислений.[15]

С этого времени Fortnow продолжал публиковать публикации по различным темам в области вычислительной сложности, включая дерандомизация, редкие языки, и машины-оракулы. Fortnow также опубликовал квантовые вычисления, теория игры, секвенирование генома, и экономика.

Работа Ланса Фортноу в области экономики включает в себя работу по теории игр, оптимальным стратегиям и прогнозам. Вместе с герцогом Вангом Фортноу исследовал классическую проблему теории игр Дилемма заключенного, расширяя проблему так, что дилемма ставится последовательно бесконечное число раз. Они исследовали, какие стратегии должны использовать игроки с учетом ограничений, которые они извлекают из своих вычислительно ограниченных множеств, и вводят «льготные периоды», чтобы предотвратить доминирование стратегий мести.[16] Фортноу также исследовал логарифмический правило рыночной оценки (LMSR) с маркет-мейкеры. Он помог показать, что цены на LMSR # P-hard и предложить метод аппроксимации для рынков перестановки цен.[17] Он также внес свой вклад в исследование поведения информированных трейдеров, работающих с маркет-мейкерами LMSR.[18]

Фортноу также является автором научно-популярной книги под названием Золотой билет: P, NP и поиск невозможного.[19], который был основан на статье, которую он ранее написал для CACM в 2009 году.[20] В своей книге Фортноу дает нетехническое введение в проблему P и NP и ее алгоритмические ограничения. Далее он описывает свою книгу и показывает, почему проблемы NP так важны на Подкаст Data Skeptic.[21]

Награды и отличия

Рекомендации

  1. ^ Лэнс Фортноу на Проект "Математическая генеалогия"
  2. ^ «Колледж вычислительной техники нанимает Фортнау, Антон руководить школами» (Пресс-релиз). Компьютерный колледж Джорджии. 19 марта 2012 г.. Получено 4 октября, 2012.
  3. ^ Факультет кафедры электротехники и информатики Северо-Западного университета
  4. ^ Транзакции ACM по теории вычислений
  5. ^ ACM SIGACT
  6. ^ Конференция IEEE по вычислительной сложности
  7. ^ Журнал вычислительной сложности
  8. ^ Дж. Марков. Помимо призов, у головоломки P-NP есть свои последствия. Нью-Йорк Таймс 7 октября 2009 г.
  9. ^ Л. Фортноу. Статус проблемы P по сравнению с NP. Коммуникации ACM 9 (2009).
  10. ^ Л. Фортноу. Сложность идеального нулевого знания. В С. Микали, редактор, Случайность и вычисление, том 5 из Достижения в компьютерных исследованиях, страницы 327-343. JAI Press, Гринвич, 1989.
  11. ^ Л. Фортноу и М. Сипсер. Существуют ли интерактивные протоколы для языков co-NP? Письма об обработке информации, 28:249-251, 1988.
  12. ^ К. Лунд, Л. Фортноу, Х. Карлофф и Н. Нисан. Алгебраические методы для интерактивных систем доказательства. Журнал ACM, 39(4):859-868, 1992.
  13. ^ А. Шамир. IP = PSPACE. Журнал ACM 39(4):869-877, 1992.
  14. ^ Л. Бабай, Л. Фортноу и К. Лунд. Недетерминированное экспоненциальное время имеет интерактивные протоколы с двумя проверяющими. Вычислительная сложность, 1(1):3-40, 1991.
  15. ^ Л. Бабай, Л. Фортнов, Л. Левин и М. Сегеди. Проверка вычислений в полилогарифмическом времени. В Материалы 23-го симпозиума ACM по теории вычислений, страницы 21-31. ACM, Нью-Йорк, 1991.
  16. ^ Л. Фортноу и Д. Ванг. Оптимальность и доминирование в повторяющихся играх с ограниченными игроками. В Материалы 26-го симпозиума ACM по теории вычислений, страницы 741-749. ACM, Нью-Йорк, 1994.
  17. ^ Ю. Чен, Л. Фортноу, Н. Ламберт, Д. Пеннок и Дж. Вортман. Сложность комбинаторный маркет-мейкеры. В Материалы 9-й конференции ACM по электронной коммерции, страницы 190-199. ACM, Нью-Йорк, 2008 г.
  18. ^ Ю. Чен, С. Димитров, Р. Сами, Д. Ривз, Д. Пеннок, Р. Хэнсон, Л. Фортноу и Р. Гонен. Рынки прогнозирования игр: стратегии равновесия с маркет-мейкером. Алгоритмика, 2009.
  19. ^ Фортнау, Лэнс. Золотой билет: P, NP и поиск невозможного. Издательство Принстонского университета, 2013 г.
  20. ^ Фортноу, Лэнс. Статус проблемы P по сравнению с NP. Коммуникации ACM, 52 (9): 78-86. Сентябрь 2009 г. Обзорная статья.
  21. ^ П против НП. Data Skeptic, 2017 г.

внешняя ссылка