Michael O. Rabin - AbsoluteAstronomy.com

For the violinist, see Michael Rabin (violinist)
Michael Rabin (violinist)
Michael Rabin was an American virtuoso violinist whose fame has continued despite his death at the age of 35.Michael Rabin was of Romanian-Jewish descent. His mother Jeanne was a Juilliard-trained pianist, and his father George was a violinist in the New York Philharmonic...

.

Michael Oser Rabin , is an Israeli

Israel

The State of Israel is a parliamentary republic located in the Middle East, along the eastern shore of the Mediterranean Sea...

computer scientist

Computer scientist

A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....

and a recipient of the Turing Award

Turing Award

The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...

Biography

Rabin was born in 1931 in Breslau, Germany

Germany

Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...

, (today Wrocław, in Poland

Poland

Poland , officially the Republic of Poland , is a country in Central Europe bordered by Germany to the west; the Czech Republic and Slovakia to the south; Ukraine, Belarus and Lithuania to the east; and the Baltic Sea and Kaliningrad Oblast, a Russian exclave, to the north...

), the son of a rabbi

Rabbi

In Judaism, a rabbi is a teacher of Torah. This title derives from the Hebrew word רבי , meaning "My Master" , which is the way a student would address a master of Torah...

. In 1935, he emigrated

Aliyah

Aliyah is the immigration of Jews to the Land of Israel . It is a basic tenet of Zionist ideology. The opposite action, emigration from Israel, is referred to as yerida . The return to the Holy Land has been a Jewish aspiration since the Babylonian exile...

with his family to Mandate Palestine. As a young boy, he was very interested in mathematics and his father sent him to the best high school in Haifa

Haifa

Haifa is the largest city in northern Israel, and the third-largest city in the country, with a population of over 268,000. Another 300,000 people live in towns directly adjacent to the city including the cities of the Krayot, as well as, Tirat Carmel, Daliyat al-Karmel and Nesher...

, where he studied under a significant practicing mathematician, Elisha Netanyahu

Elisha Netanyahu

Elisha Netanyahu was an Israeli mathematician specializing in complex analysis. Over the course of his work at the Technion he was the Dean of the Faculty of Sciences and established the separate Department of Mathematics...

, who was then a high school teacher.

After high school, he was drafted into the army during the 1948 Arab–Israeli War. The mathematician Abraham Fraenkel, who was a professor of mathematics in Jerusalem, intervened with the army command, and Rabin was discharged to study at the university in 1949.

He received an M.Sc. from Hebrew University of Jerusalem

Hebrew University of Jerusalem

The Hebrew University of Jerusalem ; ; abbreviated HUJI) is Israel's second-oldest university, after the Technion – Israel Institute of Technology. The Hebrew University has three campuses in Jerusalem and one in Rehovot. The world's largest Jewish studies library is located on its Edmond J...

in 1953 and a Ph.D.

Doctor of Philosophy

Doctor of Philosophy, abbreviated as Ph.D., PhD, D.Phil., or DPhil , in English-speaking countries, is a postgraduate academic degree awarded by universities...

from Princeton University

Princeton University

Princeton University is a private research university located in Princeton, New Jersey, United States. The school is one of the eight universities of the Ivy League, and is one of the nine Colonial Colleges founded before the American Revolution....

in 1956.

In the late 1950s, he was invited for a summer to do research for IBM

IBM

International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...

at the Lamb Estate in Westchester County, New York

Westchester County, New York

Westchester County is a county located in the U.S. state of New York. Westchester covers an area of and has a population of 949,113 according to the 2010 Census, residing in 45 municipalities...

with other promising mathematicians and scientists. It was there that he and Dana Scott

Dana Scott

Dana Stewart Scott is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California...

wrote the paper "Finite Automata and Their Decision Problems". Soon, using nondeterministic automata, they were able to re-prove Kleene's

Stephen Cole Kleene

Stephen Cole Kleene was an American mathematician who helped lay the foundations for theoretical computer science...

result that finite state machines exactly accept regular languages.

As to the origins of what was to become computational complexity theory

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, the next summer Rabin returned to the Lamb Estate. John McCarthy

John McCarthy (computer scientist)

John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...

posed a puzzle to him about spies, guards, and password which Rabin studied and soon after he wrote an article, "Degree of Difficulty of Computing a Function and Hierarchy of Recursive Sets."

Nondeterministic machines have become a key concept in computational complexity theory, particularly with the description of complexity classes P and NP.

Rabin then returned to Jerusalem, researching logic, and working on the foundations of what would later be known as computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

. He was an associate professor and the head of the Institute of Mathematics at the Hebrew University at 29 years old, and a full professor by 33. Rabin recalls, "There was absolutely no appreciation of the work on the issues of computing. Mathematicians did not recognize the emerging new field".

In 1960, he was invited by Edward F. Moore

Edward F. Moore

Edward Forrest Moore was an American professor of mathematics and computer science, the inventor of the Moore finite state machine, and an early pioneer of artificial life....

to work at Bell Labs

Bell Labs

Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...

, where Rabin introduced probabilistic automata that employ coin tosses in order to decide which state transitions to take. He showed examples of regular languages that required a very large number of states, but for which you get an exponential reduction of the number of states if you go over to probabilistic automata.

In 1969, Rabin proved that the second-order theory

Second-order logic

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....

of n successors is decidable. A key component of the proof implicitly showed determinacy

Determinacy

In set theory, a branch of mathematics, determinacy is the study of under what circumstances one or the other player of a game must have a winning strategy, and the consequences of the existence of such strategies.-Games:...

of parity game

Parity game

A parity game is played on a colored directed graph, where each node has been colored by a priority – one of finitely many natural numbers. Two players, 0 and 1, take turns moving a token along the edges of the graph, resulting in a path, called the play.The winner of a finite play is the...

s, which lie in the third level of the Borel hierarchy

Borel hierarchy

In mathematical logic, the Borel hierarchy is a stratification of the Borel algebra generated by the open subsets of a Polish space; elements of this algebra are called Borel sets. Each Borel set is assigned a unique countable ordinal number called the rank of the Borel set...

.

In 1975, Rabin finished his tenure as Rector of the Hebrew University of Jerusalem and went to the Massachusetts Institute of Technology

Massachusetts Institute of Technology

The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

in the USA as a visiting professor. Gary Miller

Gary Miller (professor)

Gary Lee Miller is a professor of Computer Science at Carnegie Mellon University, Pittsburgh, United States. In 2003, he won the ACM Paris Kanellakis Award for the Miller–Rabin primality test. He was also made an ACM Fellow in 2002....

was also there and had his polynomial

Polynomial

In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...

time test for primality based on the extended Riemann hypothesis

Generalized Riemann hypothesis

The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global L-functions, which are formally similar to the Riemann zeta-function...

. While there, Rabin invented the Miller-Rabin primality test

Miller-Rabin primality test

The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithmwhich determines whether a given number is prime,...

, a randomized algorithm that can determine very quickly (but with a tiny probability of error) whether a number is prime

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

. Rabin's method was based on previous work of Gary Miller

Gary Miller (professor)

that solved the problem deterministically with the assumption that the generalized Riemann hypothesis

Generalized Riemann hypothesis

is true, but Rabin's version of the test made no such assumption. Fast primality testing is key in the successful implementation of most public-key cryptography, and in 2003 Miller, Rabin, Robert M. Solovay

Robert M. Solovay

Robert Martin Solovay is an American mathematician specializing in set theory.Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on A Functorial Form of the Differentiable Riemann–Roch theorem...

, and Volker Strassen

Volker Strassen

Volker Strassen is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz.-Biography:Strassen was born on April 29, 1936, in Düsseldorf-Gerresheim....

were given the Paris Kanellakis Award

Paris Kanellakis Award

The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...

for their work on primality testing.

In 1976 he was invited by Joseph Traub to meet at Carnegie Mellon University

Carnegie Mellon University

Carnegie Mellon University is a private research university in Pittsburgh, Pennsylvania, United States....

and presented the primality test. After he gave that lecture, Traub had said, "No, no, this is revolutionary, and it's going to become very important."

In 1979, Rabin invented the Rabin cryptosystem

Rabin cryptosystem

The Rabin cryptosystem is an asymmetric cryptographic technique, whose security, like that of RSA, is related to the difficulty of factorization. However the Rabin cryptosystem has the advantage that the problem on which it relies has been proved to be as hard as integer factorization, which is...

, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization

Integer factorization

In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

.

In 1981, Rabin reinvented a weak variant of the technique of oblivious transfer

Oblivious transfer

In cryptography, an oblivious transfer protocol is a type of protocol in which a sender transfers one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred....

invented by Wiesner under the name of multiplexing , 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

Richard Karp

Richard Manning Karp is a computer scientist and computational theorist at the University of California, Berkeley, notable for research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto...

, created one of the most well-known efficient string search algorithms, the Rabin-Karp string search algorithm

Rabin-Karp string search algorithm

The Rabin–Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m, its average and best case running time is O in space O,...

, known for its rolling hash.

Rabin's more recent research has concentrated on computer security. He is currently the Thomas J. Watson Sr.

Thomas J. Watson

Thomas John Watson, Sr. was president of International Business Machines , who oversaw that company's growth into an international force from 1914 to 1956...

Professor of Computer Science at Harvard University

Harvard University

Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...

and Professor of Computer Science at Hebrew University. During the spring semester of 2007, he was a visiting professor at Columbia University

Columbia University

Columbia University in the City of New York is a private, Ivy League university in Manhattan, New York City. Columbia is the oldest institution of higher learning in the state of New York, the fifth oldest in the United States, and one of the country's nine Colonial Colleges founded before the...

teaching Introduction to Cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

.

Rabin is a foreign member of the United States National Academy of Sciences

United States National Academy of Sciences

The National Academy of Sciences is a corporation in the United States whose members serve pro bono as "advisers to the nation on science, engineering, and medicine." As a national academy, new members of the organization are elected annually by current members, based on their distinguished and...

, a member of the
French Academy of Sciences

French Academy of Sciences

The French Academy of Sciences is a learned society, founded in 1666 by Louis XIV at the suggestion of Jean-Baptiste Colbert, to encourage and protect the spirit of French scientific research...

and a foreign member of the Royal Society

Royal Society

The Royal Society of London for Improving Natural Knowledge, known simply as the Royal Society, is a learned society for science, and is possibly the oldest such society in existence. Founded in November 1660, it was granted a Royal Charter by King Charles II as the "Royal Society of London"...

.

He was also the PhD advisor of Saharon Shelah

Saharon Shelah

Saharon Shelah is an Israeli mathematician. He is a professor of mathematics at the Hebrew University of Jerusalem and Rutgers University in New Jersey.-Biography:...

, one of the preeminent active researchers in mathematical logic

Mathematical logic

Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

Awards

In 1976, the Turing Award

Turing Award

was awarded jointly to Rabin and Dana Scott

Dana Scott

for a paper written in 1959, the citation for which states that the award was granted:

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

In 1995, Rabin was awarded the Israel Prize

Israel Prize

The Israel Prize is an award handed out by the State of Israel and is largely regarded as the state's highest honor. It is presented annually, on Israeli Independence Day, in a state ceremony in Jerusalem, in the presence of the President, the Prime Minister, the Knesset chairperson, and the...

, in computer sciences.

In 2010, Rabin was awarded the Tel Aviv University

Tel Aviv University

Tel Aviv University is a public university located in Ramat Aviv, Tel Aviv, Israel. With nearly 30,000 students, TAU is Israel's largest university.-History:...

Dan David Prize

The Dan David Prize annually awards 3 prizes of $1 million each awarded by the Dan David Foundation and Tel Aviv University to individuals who have made an outstanding contribution in the fields of science, technology, culture or social welfare. There are three prize categories - past, present and...

("Future" category), jointly with Leonard Kleinrock

Leonard Kleinrock

Leonard Kleinrock is an American engineer and computer scientist. A computer science professor at UCLA's Henry Samueli School of Engineering and Applied Science, he made several important contributions to the field of computer networking, in particular to the theoretical side of computer networking...

and Gordon E. Moore, for Computers and Telecommunications.

External links

Short Description in an Information Science Hall of Fame at University of Pittsburgh
Oblivious transfer
Quotes from some of Professor Rabin's classes
Website for one of Rabin's courses
Description of Rabin's research by Richard J. Lipton
Richard J. Lipton
Richard Jay "Dick" Lipton is an American computer scientist who has worked in computer science theory, cryptography, and DNA computing. Lipton is presently Associate Dean of Research, Professor, and the Frederick G...

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Biography

Awards

See also

External links