Войти
| Лэнс Фортноу | |
|---|---|
| Родился | 15 августа 1963 (1963-08-15) (возраст 57) |
| Национальность | американец |
| Alma mater | Корнельский университет. Массачусетский технологический институт |
| Известен | интерактивными доказательствами |
| наградами | Стипендиат ACM, NSF Сотрудник президентского факультета, Стипендиат Фулбрайта, Премия Нерода |
| Научная карьера | |
| Области | Информатика |
| Учреждения | Технологический институт Иллинойса. Технологический институт Джорджии. Северо-Западный университет. Чикагский университет |
| Докторский советник | Майкл Сипсер |
| Докторанты | Карстен Лунд |
| Веб-сайт | http: //lance.fortnow.com /. http: //blog.c omputationalcomplexity.org/ |
Лэнс Джереми Фортноу (родился 15 августа 1963 г.) - ученый-компьютерщик, известный своими достижениями в вычислительной сложности и интерактивных системах доказательства.. В настоящее время он является деканом Научного колледжа Технологического института Иллинойса.
Лэнс Фортноу получил докторскую степень по прикладной математике в Массачусетском технологическом институте в 1989 году под руководством Майкла Сипсера. После окончания университета работал на факультете Чикагского университета (1989-1999, 2003-2007 гг.), Северо-Западного университета (2008-2012 гг.), А в последнее время - Технологический институт Джорджии (2012 – настоящее время) в качестве председателя Школы компьютерных наук.
Фортноу был главным редактором журнала ACM Transactions on Computing Theory. Он был председателем ACM SIGACT, его сменил Пол Бим. Он был председателем конференции IEEE по вычислительной сложности с 2000 по 2006 год. В 2003 году Fortnow начал один из первых блогов, посвященных теоретической информатике, и с тех пор пишет для него; с 2007 года у него был со-блоггер Уильям Гасарч. В сентябре 2009 года Фортноу привлек основное внимание к теории сложности, когда он опубликовал статью с обзором прогресса, достигнутого в решении проблемы P по сравнению с NP в Коммуникациях Ассоциации вычислительной техники.
В своих многочисленных публикациях Fortnow внес важный вклад в область вычислительной сложности. Еще будучи аспирантом Массачусетского технологического института, Фортноу показал, что не существует идеальных протоколов с нулевым разглашением для NP-полных языков, если только иерархия полиномов не рухнет. Вместе с Майклом Сипсером он также продемонстрировал, что по отношению к конкретному оракулу в co-NP существует язык, который не имеет интерактивного протокола.
В ноябре 1989 года Fortnow получил электронное письмо от Ноам Нисан показывает, что у co-NP было несколько интерактивных доказательств (MIP). Вместе с Карстеном Лундом и Ховардом Карлоффом он использовал этот результат для разработки алгебраической техники построения интерактивных систем доказательства и доказательства того, что каждый язык в иерархии полиномиального времени имеет интерактивную систему доказательства. Их работе едва исполнилось две недели, когда Ади Шамир использовал ее, чтобы доказать, что IP =PSPACE. Вскоре после этого (17 января 1990 г., менее чем через два месяца после получения электронного письма Нисана) Фортнов вместе с Ласло Бабаи и Карстеном Лундом доказали, что MIP = NEXP. Эти алгебраические методы были расширены Фортноу, Бабаем Леонидом Левином и Марио Сегеди, когда они представили новый общий механизм для проверки вычислений.
С этого времени Fortnow продолжает публиковать публикации по различным темам в области вычислительной сложности, включая дерандомизацию, разреженные языки и машины-оракулы. Фортноу также опубликовал статьи по квантовым вычислениям, теории игр, секвенированию генома и экономике.
Работа Лэнса Фортноу в области экономики включает работы по теории игр., оптимальные стратегии и прогноз. Вместе с герцогом Вангом Фортноу исследовал классическую проблему теории игр дилеммы заключенного, расширив проблему таким образом, что дилемма ставится последовательно бесконечное число раз. Они исследовали, какие стратегии должны использовать игроки с учетом ограничений, которые они извлекают из своих вычислительно ограниченных множеств, и вводят «льготные периоды», чтобы предотвратить преобладание мстительных стратегий. Fortnow также исследовал логарифмическое правило оценки рынка (LMSR) с маркет-мейкерами. Он помог показать, что ценообразование LMSR составляет # P-hard, и предложил метод аппроксимации для ценообразования на рынках перестановок. Он также внес свой вклад в исследование поведения информированных трейдеров, работающих с маркет-мейкерами LMSR.
Фортноу также является автором научно-популярной книги под названием «Золотой билет: P, NP и поиск невозможного». который был частично основан на статье, которую он ранее написал для CACM в 2009 году. В своей книге Fortnow дает нетехническое введение в проблему P и NP и ее алгоритмические ограничения. Далее он описывает свою книгу и иллюстрирует, почему проблемы NP так важны в подкасте Data Skeptic.
