Майкл Сипсер - Michael Sipser

Майкл Сипсер
MIT-Science Sipser Michael.jpg
Родившийся
Майкл Фредрик Сипсер

(1954-09-17) 17 сентября 1954 г. (возраст 66)
Бруклин, Нью-Йорк
НациональностьАмериканец
Альма-матер
Награды
Научная карьера
Поля
УчрежденияМассачусетский технологический институт
ТезисНедетерминизм и размер двусторонних конечных автоматов (1980)
ДокторантМануэль Блюм
Докторанты
Интернет сайтматематика.mit.edu/ ~ sipser/

Майкл Фредрик Сипсер (родился 17 сентября 1954 г.) - американец теоретик-информатик кто сделал ранний вклад в теория сложности вычислений. Он является профессор из Прикладная математика и был деканом науки в Массачусетский Институт Технологий.

биография

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

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

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

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

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

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

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

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

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

Личная жизнь

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

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

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

внешняя ссылка