Войти
| Майкл Сипсер | |
|---|---|
 | |
| Родился | Майкл Фредрик Сипсер ( 1954-09-17)17 сентября 1954 г. (66 лет) Бруклин, Нью-Йорк |
| Национальность | Американец |
| Альма-матер | |
| Награды | |
| Научная карьера | |
| Поля | |
| Учреждения | Массачусетский технологический институт |
| Тезис | Недетерминизм и размер двусторонних конечных автоматов (1980) |
| Докторант | Мануэль Блюм |
| Докторанты | |
| Интернет сайт | математика.mit.edu / ~ sipser / |
Майкл Фредрик Сипсер (родился 17 сентября 1954 г.) - американский ученый-теоретик, внесший ранний вклад в теорию сложности вычислений. Он является профессором по прикладной математике и был декан наук в Массачусетском технологическом институте.
Сипсер родился и вырос в Бруклине, штат Нью-Йорк, и переехал в Освего, штат Нью-Йорк, когда ему было 12 лет. Он получил степень бакалавра математики в Корнельском университете в 1974 году и степень доктора технических наук в Калифорнийском университете в Беркли в 1980 году под руководством Мануэля Блюма.
Он присоединился к Лаборатории компьютерных наук Массачусетского технологического института в качестве научного сотрудника в 1979 году, а затем был научным сотрудником IBM Research в Сан-Хосе. В 1980 году он поступил на факультет Массачусетского технологического института. 1985-1986 учебный год он проработал на факультете Калифорнийского университета в Беркли, а затем вернулся в Массачусетский технологический институт. С 2004 по 2014 год он занимал должность главы математического факультета Массачусетского технологического института. Он был назначен временным деканом Школы наук Массачусетского технологического института в 2013 году и деканом в 2014 году. Он занимал должность декана до 2020 года, когда за ним последовал Нергис Мавалвала. Он член Американской академии искусств и наук. В 2015 году он был избран членом Американского математического общества «за вклад в теорию сложности, а также за лидерство и служение математическому сообществу». Он был избран членом ACM в 2017 году.
Sipser специализируется на алгоритмах и теории сложности, в частности, на эффективных кодах исправления ошибок, интерактивных системах доказательства, случайности, квантовых вычислениях и установлении внутренней вычислительной сложности проблем. Он представил метод вероятностного ограничения для доказательства суперполиномиальных нижних оценок сложности схемы в совместной работе с Мерриком Фёрстом и Джеймсом Б. Саксом. Позднее их результат был улучшен до экспоненциальной нижней границы Эндрю Яо и Йоханом Хастадом.
В ранней теореме о дерандомизации Сипсер показал, что BPP содержится в полиномиальной иерархии, впоследствии улучшенной Питером Гачем и Клеменсом Лаутеманном, чтобы сформировать то, что теперь известно как теорема Сипсера-Гака-Лаутеманна. Sipser также установил связь между графами расширителей и дерандомизацией. Он и его аспирант Дэниел Спилман представили коды-расширители, приложение для графов-расширителей. Вместе с другим аспирантом Дэвидом Лихтенштейном Сипсер доказал, что Go - это сложная игра для PSPACE.
В теории квантовых вычислений он представил адиабатический алгоритм совместно с Эдвардом Фархи, Джеффри Голдстоуном и Сэмюэлем Гутманном.
Сипсер давно интересовался проблемой P и NP. В 1975 году он поспорил с Леонардом Адлеманом на унцию золота, что проблема будет решена с доказательством того, что P ≠ NP к концу 20 века. В 2000 году Сипсер отправил Адлеману монету американского золотого орла, потому что проблема оставалась (и остается) нерешенной.
Сипсер - автор « Введение в теорию вычислений», учебника по теоретической информатике.
Сипсер живет в Кембридже, штат Массачусетс, со своей женой Иной, и у него двое детей: дочь Рэйчел, окончившая Нью-Йоркский университет, и младший сын Аарон, окончивший Массачусетский технологический институт.
