Майкл Сипсер

Майкл Сипсер
Майкл Сипсер
Рожденный	Майкл Фредрик Сипсер ; 17 сентября 1954 г. (69 лет) ; Бруклин, Нью-Йорк
Национальность	Американский
Альма-матер	Корнелльский университет ; Калифорнийский университет в Беркли ;
Награды	Сотрудник Американской академии искусств и наук ; Член Американского математического общества ; Сотрудник Ассоциации вычислительной техники ;
	Научная карьера
Поля	Математика ; Информатика ;
Учреждения	С
Диссертация	Недетерминизм и размер двусторонних конечных автоматов (1980)
Докторантура	Мануэль Блюм
Докторанты	Лэнс Фортноу ; Sofya Raskhodnikova ; Леонард Шульман ; Дэниел Спилман ; Эндрю Сазерленд ; Ицюнь Лиза Инь ;
Веб-сайт	математика .с .edu /~sipser /

Майкл Фредрик Сипсер (родился 17 сентября 1954 г.) — американский ученый-теоретик в области информатики , внесший ранний вклад в теорию сложности вычислений . Он профессор прикладной математики и был деканом естественных наук Массачусетского технологического института .

Биография

Сипсер родился и вырос в Бруклине, штат Нью-Йорк, и переехал в Освего, штат Нью-Йорк, когда ему было 12 лет. Он получил степень бакалавра математики в Корнелльском университете в 1974 году и степень доктора технических наук в Калифорнийском университете в Беркли в 1980 году под руководством Мануэля Блюма . ^[1]^[2]

Он присоединился к Лаборатории компьютерных наук Массачусетского технологического института в качестве научного сотрудника в 1979 году, а затем был научным сотрудником в IBM Research в Сан-Хосе. В 1980 году он поступил на факультет Массачусетского технологического института. 1985–1986 учебный год он провел на факультете Калифорнийского университета в Беркли, а затем вернулся в Массачусетский технологический институт. С 2004 по 2014 год он занимал должность руководителя математического факультета Массачусетского технологического института. Он был назначен временным деканом Школы наук Массачусетского технологического института в 2013 году и деканом в 2014 году. ^[3] Он занимал пост декана до 2020 года, когда его сменил Нергис Мавалвала . ^[4] Он является членом Американской академии искусств и наук. ^[5] В 2015 году он был избран членом Американского математического общества «за вклад в теорию сложности, а также за лидерство и служение математическому сообществу». ^[6] В 2017 году он был избран членом ACM . ^[7]

Научная карьера

Сипсер специализируется на алгоритмах и теории сложности , в частности на эффективных кодах исправления ошибок, интерактивных системах доказательства, случайности, квантовых вычислениях и установлении внутренней вычислительной сложности задач. Он представил метод вероятностного ограничения для доказательства суперполиномиальных нижних границ сложности схемы в совместной работе с Мерриком Ферстом и Джеймсом Б. Саксом . ^[8] до экспоненциальной нижней границы Их результат позже был улучшен Эндрю Яо и Йоханом Хостадом . ^[9]

В ранней теореме о дерандомизации Сипсер показал, что BPP содержится в полиномиальной иерархии , ^[10] впоследствии улучшенная Петером Гачем и Клеменсом Лаутеманном и образовавшая то, что сейчас известно как теорема Сипсера-Гача-Лаутмана . Сипсер также установил связь между графами-расширителями и дерандомизацией. ^[11] Он и его аспирант Дэниел Спилман представили расширительные коды — применение расширительных графов. ^[12] Вместе с аспирантом Дэвидом Лихтенштейном Сипсер доказал, что Go — это PSPACE . сложное ^[13]

В теории квантовых вычислений он представил адиабатический алгоритм совместно с Эдвардом Фархи , Джеффри Голдстоуном и Сэмюэлем Гутманном. ^[14]

Сипсер уже давно интересуется проблемой P и NP . на унцию золота В 1975 году он поспорил с Леонардом Адлеманом , что проблема будет решена с доказательством того, что P≠NP к концу 20-го века. Сипсер отправил Адлеману монету «Американский золотой орел» в 2000 году, потому что проблема оставалась (и остается) нерешенной. ^[15]

Известные книги

Сипсер — автор книги «Введение в теорию вычислений» . ^[16] учебник по теоретической информатике .

Личная жизнь

Сипсер живет в Кембридже, штат Массачусетс, со своей женой Иной, у них двое детей: дочь Рэйчел, окончившая Нью-Йоркский университет, и младший сын Аарон, окончивший Массачусетский технологический институт. ^[1]

Ссылки

^ Перейти обратно: ^а ^б Трафтон, Энн, «Майкл Сипсер назначен деканом Школы естественных наук: Сипсер исполнял обязанности временного декана после ухода Марка Кастнера» , Офис новостей Массачусетского технологического института, 5 июня 2014 г.
^ Майкл Сипсер в проекте «Математическая генеалогия»
^ Математический институт Массачусетского технологического института | Справочник людей , заархивированный 18 декабря 2008 г. в Wayback Machine.
^ «Школа науки | История Массачусетского технологического института» . Проверено 25 августа 2020 г.
^ «Членство» . Американская академия искусств и наук . Проверено 23 сентября 2014 г.
^ Класс членов AMS , Американского математического общества 2016 г. , получено 16 ноября 2015 г.
^ ACM награждает стипендиатов 2017 года за вклад в трансформацию и развитие технологий в эпоху цифровых технологий , Ассоциация вычислительной техники, 11 декабря 2017 г. , получено 13 ноября 2017 г.
^ Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Теория математических систем . 17 (1): 13–27. дои : 10.1007/BF01744431 . МР 0738749 . S2CID 14677270 .
^ «Виньетка исследования: все сложные проблемы | Институт теории вычислений Саймонса» . simons.berkeley.edu . 30 июля 2015 года . Проверено 17 сентября 2015 г.
^ Сипсер, Майкл (1983). «Теоретико-сложный подход к случайности». Материалы 15-го симпозиума ACM по теории вычислений .
^ Сипсер, Майкл (1986). «Расширители, случайность или время против пространства». Структура в теории сложности: материалы конференции, состоявшейся в Калифорнийском университете в Беркли, 2–5 июня 1986 г. Конспекты лекций по информатике. Том. 223. С. 325–329. дои : 10.1007/3-540-16486-3_108 . ISBN 978-3-540-16486-9 .
^ Сипсер, Майкл; Спилман, Дэниел (1996). «Коды расширителя» (PDF) . Транзакции IEEE по теории информации . 42 (6): 1710–1722. дои : 10.1109/18.556667 .
^ Лихтенштейн, Дэвид; Сипсер, Майкл (1 апреля 1980 г.). «GO — это сложно в полиномиальном пространстве» . Дж. АКМ . 27 (2): 393–401. дои : 10.1145/322186.322201 . ISSN 0004-5411 . S2CID 29498352 .
^ Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм; Сипсер, Майкл (28 января 2000 г.). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106 .
^ Павлус, Джон (01 января 2012 г.). «Машины бесконечности». Научный американец . 307 (3): 66–71. Бибкод : 2012SciAm.307c..66P . doi : 10.1038/scientificamerican0912-66 . ПМИД 22928263 .
^ Сипсер, Майкл (27 июня 2012 г.). Введение в теорию вычислений (3-е изд.). Cengage Обучение. ISBN 978-1133187790 .

Внешние ссылки

Персональная домашняя страница в MIT

[MITNEWS06052014-1] Перейти обратно: ^а ^б Трафтон, Энн, «Майкл Сипсер назначен деканом Школы естественных наук: Сипсер исполнял обязанности временного декана после ухода Марка Кастнера» , Офис новостей Массачусетского технологического института, 5 июня 2014 г.

[2] Майкл Сипсер в проекте «Математическая генеалогия»

[3] Математический институт Массачусетского технологического института | Справочник людей , заархивированный 18 декабря 2008 г. в Wayback Machine.

[4] «Школа науки | История Массачусетского технологического института» . Проверено 25 августа 2020 г.

[5] «Членство» . Американская академия искусств и наук . Проверено 23 сентября 2014 г.

[6] Класс членов AMS , Американского математического общества 2016 г. , получено 16 ноября 2015 г.

[7] ACM награждает стипендиатов 2017 года за вклад в трансформацию и развитие технологий в эпоху цифровых технологий , Ассоциация вычислительной техники, 11 декабря 2017 г. , получено 13 ноября 2017 г.

[8] Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Теория математических систем . 17 (1): 13–27. дои : 10.1007/BF01744431 . МР 0738749 . S2CID 14677270 .

[9] «Виньетка исследования: все сложные проблемы | Институт теории вычислений Саймонса» . simons.berkeley.edu . 30 июля 2015 года . Проверено 17 сентября 2015 г.

[10] Сипсер, Майкл (1983). «Теоретико-сложный подход к случайности». Материалы 15-го симпозиума ACM по теории вычислений .

[11] Сипсер, Майкл (1986). «Расширители, случайность или время против пространства». Структура в теории сложности: материалы конференции, состоявшейся в Калифорнийском университете в Беркли, 2–5 июня 1986 г. Конспекты лекций по информатике. Том. 223. С. 325–329. дои : 10.1007/3-540-16486-3_108 . ISBN 978-3-540-16486-9 .

[12] Сипсер, Майкл; Спилман, Дэниел (1996). «Коды расширителя» (PDF) . Транзакции IEEE по теории информации . 42 (6): 1710–1722. дои : 10.1109/18.556667 .

[13] Лихтенштейн, Дэвид; Сипсер, Майкл (1 апреля 1980 г.). «GO — это сложно в полиномиальном пространстве» . Дж. АКМ . 27 (2): 393–401. дои : 10.1145/322186.322201 . ISSN 0004-5411 . S2CID 29498352 .

[14] Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм; Сипсер, Майкл (28 января 2000 г.). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106 .

[15] Павлус, Джон (01 января 2012 г.). «Машины бесконечности». Научный американец . 307 (3): 66–71. Бибкод : 2012SciAm.307c..66P . doi : 10.1038/scientificamerican0912-66 . ПМИД 22928263 .

[16] Сипсер, Майкл (27 июня 2012 г.). Введение в теорию вычислений (3-е изд.). Cengage Обучение. ISBN 978-1133187790 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Базы данных авторитетного контроля
Международный	ЯВЛЯЮТСЯ ВИАФ WorldCat
Национальный	Норвегия Германия Израиль Соединенные Штаты Япония Нидерланды Польша
академики	Ассоциация вычислительной техники ЦиНии ДБЛП MathSciNet Проект математической генеалогии zbMATH
Другой	ИдРеф