Michael O. Rabin Article Index for
Michael O 		Website Links For
Michael 		 

Information About

Michael O. Rabin
  CATEGORIES ABOUT MICHAEL O. RABIN
   
1931 births
   
rabin, michael o.
   
american computer scientists
   
erdős number 2
   
rabin, michel o.
   
living people
   
members and associates of the united states national academy of sciences
   
turing award laureates
   
modern cryptographers
   
israel prize recipients
   
german jews
   
logicians
   
SHOPPER'S DELIGHT
 
Shop For:  
Department
Price Minimum:
Price Maximum:
      



Michael Oser Rabin (born 1931 in Breslau , Germany , today in Poland ) is a noted Computer Scientist and a recipient of the Turing Award , the most prestigious award in the field.

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 .

The citation for the Turing Award, awarded in 1976 jointly to Rabin and Dana Scott for a paper written in 1959 , states that the award was granted:


''For their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field.''


Nondeterministic machines have become a key concept in Computational Complexity Theory , particularly with the description of Complexity Classes P And NP .

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 . Fast primality testing is key in the successful implementation of most public-key cryptography.

In 1979 , Rabin invented the Rabin Cryptosystem , which was the first asymmetric cryptosystem whose security was proved equivalent to the intractability of Integer Factorization .

In 1981 , Rabin invented the technique of Oblivious Transfer , allowing a sender to transmit a message to a receiver where the receiver has some probability between 0 and 1 of learning the message, with the sender being unaware whether the receiver was able to do so.

In 1987 , Rabin, together with Richard Karp , created one of the most well-known efficient String Search Algorithm s, the Rabin-Karp String Search Algorithm , known for its rolling hash.

Rabin's more recent research has concentrated on computer security. He is currently the Thomas J. Watson Sr. Professor of Computer Science at Harvard University and Professor of Computer Science at Hebrew University .


SEE ALSO



EXTERNAL LINKS