Michael Oser Rabin (Hebrew: מִיכָאֵל אֹשֶׁר רַבִּין, born September 1, 1931 in Breslau, Germany, today in Poland) is a computer scientist and a recipient of the Turing Award.
Rabin was born as the son of a rabbi in what was then known as Breslau (it became Wrocław, and part of Poland, after the Second World War). He received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton University in 1956.
Nondeterministic machi...
more
Michael Oser Rabin (Hebrew: מִיכָאֵל אֹשֶׁר רַבִּין, born September 1, 1931 in Breslau, Germany, today in Poland) is a computer scientist and a recipient of the Turing Award.
Rabin was born as the son of a rabbi in what was then known as Breslau (it became Wrocław, and part of Poland, after the Second World War). He received an M.Sc. from Hebrew University of Jerusalem in 1953 and a Ph.D. from Princeton University in 1956.
Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP.
In 1969, Rabin proved that the second-order theory of n successors is decidable. A key component of the proof implicitly showed determinacy of parity games, which lie in the third level of the Borel hierarchy.
In 1975, Rabin also invented the Miller-Rabin primality test, a randomized algorithm that can determine very quickly (but with a tiny probability of error) whether a number is prime. Rabin's method was based...
less
