Майкл Сипсер

Майкл Сипсер
Майкл Сипсер
Рожденный	Майкл Фредрик Сипсер ; 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 ]}

Ссылки

^ Jump up to: ^а ^б Трафтон, Энн, «Майкл Сипсер назначен деканом Школы естественных наук: Сипсер исполнял обязанности временного декана после ухода Марка Кастнера» , Офис новостей Массачусетского технологического института, 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] Jump up to: ^а ^б Трафтон, Энн, «Майкл Сипсер назначен деканом Школы естественных наук: Сипсер исполнял обязанности временного декана после ухода Марка Кастнера» , Офис новостей Массачусетского технологического института, 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
Другой	ИдРеф