Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Американский теоретический компьютерный ученый (род. 1954)
American theoretical computer scientist (born 1954)
Майкл Фредрик Сипсер (род. 17 сентября 1954) — американский теоретический компьютерный ученый, сделавший значительный вклад в теорию вычислительной сложности на раннем этапе её развития. Он является профессором прикладной математики и занимал должность декана факультета естественных наук в Массачусетском технологическом институте.
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.
Биография
Сипсер родился и вырос в Бруклине, Нью-Йорк, и переехал в Освего, Нью-Йорк, когда ему было 12 лет. Он получил степень бакалавра математики в Корнеллском университете в 1974 году и степень доктора философии в области инженерии в Калифорнийском университете в Беркли в 1980 году под руководством Мануэля Блума. В 1979 году он присоединился к Лаборатории компьютерных наук МТИ в качестве научного сотрудника, а затем работал в исследовательском составе IBM Research в Сан-Хосе. В 1980 году он присоединился к преподавательскому составу МТИ. Он провёл 1985–1986 учебный год в качестве преподавателя Калифорнийского университета в Беркли, а затем вернулся в МТИ. С 2004 по 2014 год он возглавлял математический факультет МТИ. В 2013 году он был назначен исполняющим обязанности декана Школы наук МТИ, а в 2014 году – деканом. Он занимал должность декана до 2020 года, когда его сменила Нергис Мавалвала. Он является членом Американской академии искусств и наук. В 2015 году он был избран членом Американского математического общества «за вклад в теорию сложности, а также за лидерство и служение математическому сообществу». В 2017 году он был избран членом ACM.
Sipser was born and raised in Brooklyn, New York and moved to Oswego, New York when he was 12 years old. He earned his BA in mathematics from Cornell University in 1974 and his PhD in engineering from the University of California at Berkeley in 1980 under the direction of Manuel Blum. He joined MIT's Laboratory for Computer Science as a research associate in 1979 and then was a Research Staff Member at IBM Research in San Jose. In 1980, he joined the MIT faculty. He spent the 1985–1986 academic year on the faculty of the University of California at Berkeley and then returned to MIT. From 2004 until 2014, he served as head of the MIT Mathematics department. He was appointed Interim Dean of the MIT School of Science in 2013 and Dean in 2014. He served as Dean until 2020, when he was followed by Nergis Mavalvala. He is a fellow of the American Academy of Arts and Sciences. In 2015 he was elected as a fellow of the American Mathematical Society "for contributions to complexity theory and for leadership and service to the mathematical community." He was elected as an ACM Fellow in 2017.
Научная карьера
Сипсер специализируется на алгоритмах и теории сложности, в частности на эффективных кодах, исправляющих ошибки, интерактивных системах доказательств, случайности, квантовых вычислениях и установлении внутренней вычислительной сложности задач. Он ввёл метод вероятностного ограничения для доказательства сверхполиномиальных нижних оценок сложности булевых схем в совместной работе с Мерриком Фурстом и Джеймсом Б. Саксом. Их результат впоследствии был улучшен до экспоненциальной нижней оценки Эндрю Яо и Йоханом Хостадом. В ранней теореме о дерандомизации Сипсер показал, что класс BPP содержится в полиномиальной иерархии, что впоследствии было улучшено Питером Гачсом и Клеменсом Лаутманном и стало известно как теорема Сипсера — Гача — Лаутманна. Сипсер также установил связь между расширяющимися графами и дерандомизацией. Он и его аспирант Дэниел Спилман представили экспандерные коды – применение расширяющихся графов. Вместе с сокурсником Дэвидом Лихтенштейном Сипсер доказал, что игра Го является PSPACE-полной. В теории квантовых вычислений он совместно с Эдвардом Фархи, Джеффри Голдстоуном и Сэмюэлем Гутманом ввёл адиабатический алгоритм. Сипсер давно интересуется проблемой P против NP. В 1975 году он заключил пари с Леонардом Адлеманом об унции золота, что проблема будет решена с доказательством P≠NP к концу 20-го века. В 2000 году Сипсер отправил Адлеману золотую монету American Gold Eagle, поскольку проблема оставалась (и остаётся) нерешённой.
Sipser specializes in algorithms and complexity theory, specifically efficient error correcting codes, interactive proof systems, randomness, quantum computation, and establishing the inherent computational difficulty of problems. He introduced the method of probabilistic restriction for proving super polynomial lower bounds on circuit complexity in a paper joint with Merrick Furst and James B. Saxe. Their result was later improved to be an exponential lower bound by Andrew Yao and Johan Håstad. In an early derandomization theorem, Sipser showed that BPP is contained in the polynomial hierarchy, subsequently improved by Peter Gács and Clemens Lautemann to form what is now known as the Sipser Gács Lautemann theorem. Sipser also established a connection between expander graphs and derandomization. He and his PhD student Daniel Spielman introduced expander codes, an application of expander graphs. With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard. In quantum computation theory, he introduced the adiabatic algorithm jointly with Edward Farhi, Jeffrey Goldstone, and Samuel Gutmann. Sipser has long been interested in the P versus NP problem. In 1975, he wagered an ounce of gold with Leonard Adleman that the problem would be solved with a proof that P≠NP by the end of the 20th century. Sipser sent Adleman an American Gold Eagle coin in 2000 because the problem remained (and remains) unsolved.
Известные книги
Сипсер — автор учебника «Введение в теорию вычислений», предназначенного для изучения теоретической информатики.
Sipser is the author of Introduction to the Theory of Computation, a textbook for theoretical computer science.
Личная жизнь
Сипсер живет в Кембридже, штат Массачусетс, со своей женой Иной и имеет двоих детей: дочь Рейчел, закончившую Нью-Йоркский университет, и младшего сына Аарона, который окончил MIT.
Sipser lives in Cambridge, Massachusetts with his wife, Ina, and has two children: a daughter, Rachel, who graduated from New York University, and a younger son, Aaron, who graduated from MIT.