Михаэль Ошер Рабин

Михаэль Рабин

Michael Rabin

 

Дата рождения

1 сентября 1931 года

Место рождения

Вроцлав, Германия

Известные ученики

Сахарон Шелах

Известен как

Алгоритм Рабина — Карпа, Тест Миллера — Рабина

Михаэль Ошер Рабин (Майкл Рабин, Михаэль Озер Рабин, нем. Michael Oser Rabin, ивр. מיכאל עוזר רבין) — израильский учёный в области теории вычислительных систем и математик.

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

Родился 1 сентября 1931 года в Бреслау в семье раввина Исраэля Аврахама Рабина.

В 1935 году с семьёй репатриировался в Эрец-Исраэль.

В 1948 году, во время Войны Израиля за независимость был призван в АОИ.

В 1953 году получил степень магистра в Еврейском университете в Иерусалиме.

В 1956 году получил докторскую степень в Принстонском университете.

В 1956−1958 годах преподавал математику в Принстонском университете.

С 1958 года — преподаватель математики в Еврейском университете в Иерусалиме (с 1965 года — профессор); в 1964−1966 годах — директор Института математики, в 1970−1971 годах — глава отделения компьютерных наук, в 1972−1975 годах — ректор, в 1976−1980 годах — проректор.

В 1969 году обобщил теорему Бьюхи на случай более одной функции следования, чем показал разрешимость соответствующей теории второго порядка. В ходе ведения доказательства Рабин доказал детерминированность игр на чётность (parity games).

В 1975 году был избран членом Американской академии искусств и наук.

В том же 1975 году Гари Миллер разработал новый тест простоты, который был модифицирован Рабином в 1980 году. Тест Миллера — Рабина — вероятностный полиномиальный алгоритм, способный очень эффективно, но с ненулевой вероятностью ошибки, проверить число на простоту. Спустя 4 года, Рабин разработал первую асимметричную криптосистему, сложность взлома которой сравнима с проблемой факторизации целых чисел.

С 1981 года — профессор Гарвардского университета.

В том же 1981 году изобрёл протокол передачи данных с забыванием (oblivious transfer) — надёжную технику передачи информации, при которой отправитель не получает подтверждения того, дошло ли сообщение до получателя.

В 1982 году был избран членом Израильской АН.

В 1984 году был избран членом Национальной АН США.

В 1987 году совместно с Ричардом Карпом разработал алгоритм поиска образца (подстроки) в строке.

По данным на сентябрь 2008 года занимается исследованиями в области компьютерной безопасности и преподаёт в Иерусалиме и Гарварде.

Был удостоен следующих наград и премий: в 1960 году — Премия Вейцмана по точным наукам, в 1973 году — Ротшильдовская премия по математике, в 1976 году — Премия Тьюринга совместно с Дана Скоттом «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов, ставших несомненно полезной концепцией. Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области» Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений, где с их помощью описывается класс NP, в 1980 году — Премия Харви, в 1985 году — Гиббсовская лекция, в 1995 году — Государственная премия Израиля по математике, в 2000 году — Премия Чарльза Беббиджа от IEEE, в 2001 году — Мемориальные лекции Вейцмана, в 2003 году — Премия Париса Канеллакиса , в 2004 году — Премия EMET, в 2010 году — Премия Дэна Дэвида, в 2015 году — Премия Дейкстры.

Имеет звания почётного профессора в Университет Бордо (1996), Хайфском университете (1996), Открытом университете Израиля (почётный член, 1999), Университете имени Бен-Гуриона (2000) и Вроцлавском университете (2007).

Получил результаты мирового значения в ряде разделов теоретической и прикладной математики — математической логике, теории алгоритмов, математической теории автоматов, теории вероятностных алгоритмов, теории компьютерной защиты и некоторых других. Рабин — один из крупнейших в мире специалистов в области математического обеспечения надежного функционирования компьютерных систем и защиты информации от несанкционированного доступа.

Его дочь, Таль Рабин, руководит научной группой Cryptography and Privacy Research Group в компании IBM.