Майкл Сипсер - Michael Sipser
Майкл Сипсер | |
---|---|
Родился |
Майкл Фредрик Сипсер
17 сентября 1954 г. |
Национальность | Американец |
Альма-матер | |
Награды | |
Научная карьера | |
Поля | |
Учреждения | Массачусетский технологический институт |
Тезис | Недетерминизм и размер двусторонних конечных автоматов (1980) |
Докторант | Мануэль Блюм |
Докторанты | |
Интернет сайт | математика |
Майкл Фредрик Сипсер (родился 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 году Сипсер отправил Адлеману монету американского золотого орла, потому что проблема оставалась (и остается) нерешенной.
Известные книги
Сипсер - автор « Введение в теорию вычислений» , учебника по теоретической информатике .
Личная жизнь
Сипсер живет в Кембридже, штат Массачусетс, со своей женой Иной, и у него двое детей: дочь Рэйчел, окончившая Нью-Йоркский университет, и младший сын Аарон, окончивший Массачусетский технологический институт.