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

Это статья о человеке, который недавно умер.

Информация об обстоятельствах смерти человека может быстро меняться по мере того, как эти факты становятся известны. Если в эту статью внесены деструктивные правки, пожалуйста, обратитесь к администраторам.

Михаэль Озёр Рабин (нем. Michael Oser Rabin, ивр.מִיכָאֵל עוזר רַבִּין‎, 1 сентября1931, Бреслау — 14 апреля2026, Раанана) — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга.

Родился в семье уроженца ПроскуровараввинаИсраэля Аврахама Рабина. В 1935 году его семья эмигрировала в Палестину. В юном возрасте обучался математике у Элиши Нитаньяху^[4]. В 1953 году он получил степень магистра наук^[англ.], окончив учёбу в Еврейском университете в Иерусалиме. В 1956 году под руководством Алонзо Чёрч защитил диссертацию в Принстонском университете и стал доктором философии.

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

Среди учеников — лауреат премии Вольфа по математике Саарон Шелах.

Дочь — Таль Рабин, руководитель научно-исследовательской группы по криптографии и конфиденциальности в корпорации IBM.

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

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

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

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

• Биография Рабина на сайте Гарвардского университета  (недоступная ссылка с 13-05-2013 [4723 дня] — история) (англ.)
• Karp, RM; Rabin, MO (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development. 31 (2): 249—260.
• Harvard awards 10 honorary degrees