Майкл О. Рабин - Michael O. Rabin

Майкл Осер Рабин
М.О. Рабин.jpg
Родился ( 1931-09-01 )1 сентября 1931 г. (89 лет)
Национальность Израильский
Альма-матер Еврейский университет Иерусалима ( MSc )
Принстонский университет ( PhD )
Известен Тест на простоту Миллера – Рабина
Криптосистема Рабина
Незаметный перенос
Алгоритм поиска строки Рабина – Карпа
Недетерминированные конечные автоматы
Рандомизированные алгоритмы
Награды Премия Тьюринга (1976)
Премия Пэрис Канеллакис (2003)
Премия Израиля Премия
EMET Премия
Харви Премия
Дэна Дэвида Премия
Дейкстры
IEEE Computer Society Премия Чарльза Бэббиджа
Научная карьера
Поля Информатика
Учреждения Гарвардский университет
Еврейский университет Иерусалима
Колумбийский университет
Тезис Рекурсивная неразрешимость теоретико-групповых задач  (1957)
Докторант Церковь Алонсо
Докторанты

Майкл Осер Рабин ( иврит : מִיכָאֵל עוזר רַבִּין ; родился 1 сентября 1931 г.) - израильский математик и ученый-компьютерщик , лауреат премии Тьюринга .

биография

ранняя жизнь и образование

Рабин родился в 1931 году в Бреслау , Германия (сегодня Вроцлав , Польша ), в семье раввина . В 1935 году он эмигрировал со своей семьей в подмандатную Палестину . В детстве он очень интересовался математикой, и отец отправил его в лучшую среднюю школу Хайфы , где он учился у математика Элиша Нетаньяху , который тогда был учителем средней школы.

Рабин окончил еврейскую школу Реали в Хайфе в 1948 году и был призван в армию во время арабо-израильской войны 1948 года . Математик Абрахам Френкель , который был профессором математики в Иерусалиме , вмешался в армейское командование, и Рабин был отчислен на учебу в университет в 1949 году.

Он получил степень магистра наук. окончил Еврейский университет в Иерусалиме в 1953 году и получил степень доктора философии. из Принстонского университета в 1956 году.

Карьера

Рабин стал адъюнкт-профессором математики в Калифорнийском университете в Беркли (1961–62) и Массачусетском технологическом институте (1962–63). Прежде чем перейти в Гарвардский университет в качестве профессора компьютерных наук Гордона Маккея в 1981 году, он был профессором Еврейского университета.

В конце 1950-х его пригласили на лето для проведения исследований для IBM в Lamb Estate в округе Вестчестер, штат Нью-Йорк, вместе с другими многообещающими математиками и учеными. Именно там он и Дана Скотт написали статью «Конечные автоматы и их проблемы принятия решений». Вскоре, используя недетерминированные автоматы, они смогли повторно доказать результат Клини о том, что конечные автоматы точно принимают регулярные языки.

Что касается истоков того, что должно было стать теорией вычислительной сложности , следующим летом Рабин вернулся в Lamb Estate. Джон Маккарти поставил перед ним загадку о шпионах, охранниках и паролях, которую Рабин изучил и вскоре после того, как написал статью «Степень сложности вычисления функции и иерархии рекурсивных множеств».

Недетерминированные машины стали ключевым понятием в теории сложности вычислений, особенно с описанием классов сложности P и NP .

Затем Рабин вернулся в Иерусалим, исследуя логику и работая над основами того, что позже будет известно как информатика . В 29 лет он был адъюнкт-профессором и главой Института математики Еврейского университета, а к 33 годам стал профессором. Рабин вспоминает: «Работа по вопросам вычислений не получила абсолютно никакой оценки. признать возникающее новое поле ".

В 1960 году он был приглашен Эдвардом Ф. Муром на работу в Bell Labs , где Рабин представил вероятностные автоматы, которые используют подбрасывание монеты, чтобы решить, какие переходы между состояниями предпринять. Он показал примеры регулярных языков, для которых требуется очень большое количество состояний, но для которых вы получите экспоненциальное уменьшение количества состояний, если перейти к вероятностным автоматам.

В 1969 году Рабин доказал , что теория второго порядка из п преемников разрешима . Ключевой компонент доказательства неявно показал детерминированность о четности играх , которые лежат в третьем уровне иерархии Борель .

В 1975 году Рабин закончил свою должность ректора Еврейского университета в Иерусалиме и отправился в Массачусетский технологический институт в США в качестве приглашенного профессора. Гэри Миллер также был там и прошел свой полиномиальный временной тест на простоту, основанный на расширенной гипотезе Римана . Находясь там, Рабин изобрел тест простоты Миллера – Рабина , рандомизированный алгоритм, который может очень быстро (но с крошечной вероятностью ошибки) определить, является ли число простым . Метод Рабина был основан на предыдущей работе Гэри Миллера , в которой проблема решалась детерминированно с предположением, что обобщенная гипотеза Римана верна, но версия теста Рабина не делала такого предположения. Быстрое тестирование на простоту является ключом к успешной реализации большей части криптографии с открытым ключом, и в 2003 году Миллер, Рабин, Роберт М. Соловей и Фолькер Штрассен были удостоены Премии Париса Канеллакиса за их работу по проверке простоты.

В 1976 году он был приглашен Джозефом Траубом на встречу в Университете Карнеги-Меллона и представил тест на простоту. После того, как он прочитал ту лекцию, Трауб сказал: «Нет, нет, это революционно, и это станет очень важным».

В 1979 году Рабин изобрел криптосистему Рабина , первую асимметричную криптосистему, безопасность которой оказалась эквивалентной неразрешимости целочисленной факторизации .

В 1981 году Рабин заново изобрел слабый вариант техники неявной передачи, изобретенной Визнером под названием мультиплексирование, позволяя отправителю передать сообщение получателю, где получатель имеет некоторую вероятность от 0 до 1 изучить сообщение, с отправитель не знает, смог ли получатель это сделать.

В 1987 году Рабин вместе с Ричардом Карпом создал один из самых известных эффективных алгоритмов поиска по строкам , алгоритм поиска по строкам Рабина – Карпа , известный своим скользящим хешем.

Недавнее исследование Рабина было сосредоточено на компьютерной безопасности. В настоящее время он является профессором компьютерных наук Томаса Дж. Уотсона-старшим в Гарвардском университете и профессором компьютерных наук в Еврейском университете . В весеннем семестре 2007 года он был приглашенным профессором Колумбийского университета и преподавал введение в криптографию .

Награды и почести

Рабин - иностранный член Национальной академии наук США , член Французской академии наук и иностранный член Королевского общества .

В 1976 году премия Тьюринга была присуждена совместно Рабину и Дане Скотт за работу, написанную в 1959 году, в цитате говорится, что награда была присуждена:

За их совместную статью «Конечные автоматы и проблемы их решения», в которой была представлена ​​идея недетерминированных машин, которая оказалась чрезвычайно ценной концепцией. Их (Scott & Rabin) [ sic ] классическая статья была постоянным источником вдохновения для дальнейшей работы в этой области.

В 1995 году Рабин был удостоен премии Израиля в области компьютерных наук. В 2010 году Рабин был удостоен премии Тель-Авивского университета Дэна Дэвида (категория «Будущее») совместно с Леонардом Клейнроком и Гордоном Э. Муром за компьютеры и телекоммуникации. Рабин был удостоен звания почетного доктора наук Гарвардского университета в 2017 году.

Смотрите также

использованная литература

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