stringtranslate.com

Майкл Сипсер

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

биография

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

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

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

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

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

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

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

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

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

Личная жизнь

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

Рекомендации

  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. MR  0738749. S2CID  14677270.
  9. ^ «Виньетка исследования: сложные проблемы на всем пути | Институт теории вычислений Саймонса» . simons.berkeley.edu . 30 июля 2015 года . Проверено 17 сентября 2015 г.
  10. ^ Сипсер, Майкл (1983). «Теоретико-сложный подход к случайности». Материалы 15-го симпозиума ACM по теории вычислений .
  11. ^ Сипсер, Майкл (1986). «Расширители, случайность или время против пространства». Структура в теории сложности . Конспекты лекций по информатике. Том. 223. С. 325–329. дои : 10.1007/3-540-16486-3_108. ISBN 978-3-540-16486-9. {{cite book}}: |journal=игнорируется ( помощь )
  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. ^ Павлус, Джон (1 января 2012 г.). «Машины бесконечности». Научный американец . 307 (3): 66–71. Бибкод : 2012SciAm.307c..66P. doi : 10.1038/scientificamerican0912-66. ПМИД  22928263.
  16. ^ Сипсер, Майкл (27 июня 2012 г.). Введение в теорию вычислений (3-е изд.). Cengage Обучение. ISBN 978-1133187790.

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