Michael O. Rabin
   HOME

TheInfoList



OR:

Michael Oser Rabin ( he, מִיכָאֵל עוזר רַבִּין; born September 1, 1931) is an Israeli
mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...
and
computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...
and a recipient of the
Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
.


Biography


Early life and education

Rabin was born in 1931 in Breslau,
Germany Germany,, officially the Federal Republic of Germany, is a country in Central Europe. It is the second most populous country in Europe after Russia, and the most populous member state of the European Union. Germany is situated betwe ...
(today
Wrocław Wrocław (; german: Breslau, or . ; Silesian German: ''Brassel'') is a city in southwestern Poland and the largest city in the historical region of Silesia. It lies on the banks of the River Oder in the Silesian Lowlands of Central Europe, rou ...
, in
Poland Poland, officially the Republic of Poland, is a country in Central Europe. It is divided into 16 administrative provinces called voivodeships, covering an area of . Poland has a population of over 38 million and is the fifth-most populous ...
), the son of a
rabbi A rabbi () is a spiritual leader or religious teacher in Judaism. One becomes a rabbi by being ordained by another rabbi – known as ''semikha'' – following a course of study of Jewish history and texts such as the Talmud. The basic form of ...
. In 1935, he
emigrated Emigration is the act of leaving a resident country or place of residence with the intent to settle elsewhere (to permanently leave a country). Conversely, immigration describes the movement of people into one country from another (to permanentl ...
with his family to
Mandate Palestine Mandatory Palestine ( ar, فلسطين الانتدابية '; he, פָּלֶשְׂתִּינָה (א״י) ', where "E.Y." indicates ''’Eretz Yiśrā’ēl'', the Land of Israel) was a geopolitical entity established between 1920 and 1948 i ...
. As a young boy, he was very interested in mathematics and his father sent him to the best high school in
Haifa Haifa ( he, חֵיפָה ' ; ar, حَيْفَا ') is the third-largest city in Israel—after Jerusalem and Tel Aviv—with a population of in . The city of Haifa forms part of the Haifa metropolitan area, the third-most populous metropol ...
, where he studied under mathematician
Elisha Netanyahu Elisha Netanyahu ( he, אֱלִישָׁע נְתַנְיָהוּ; December 21, 1912 – April 3, 1986) 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 ...
, who was then a high school teacher. Rabin graduated from the
Hebrew Reali School , motto_translation = ''Walk Humbly'' , address = Hertzel 16 , city = Haifa , zipcode = 3312103 , country = Israel , coordinates = , other_name ...
in Haifa in 1948, and was drafted into the army during the
1948 Arab–Israeli War The 1948 (or First) Arab–Israeli War was the second and final stage of the 1948 Palestine war. It formally began following the end of the British Mandate for Palestine at midnight on 14 May 1948; the Israeli Declaration of Independence had ...
. The mathematician
Abraham Fraenkel Abraham Fraenkel ( he, אברהם הלוי (אדולף) פרנקל; February 17, 1891 – October 15, 1965) was a German-born Israeli mathematician. He was an early Zionist and the first Dean of Mathematics at the Hebrew University of Jerusalem. ...
, who was a professor of mathematics in
Jerusalem Jerusalem (; he, יְרוּשָׁלַיִם ; ar, القُدس ) (combining the Biblical and common usage Arabic names); grc, Ἱερουσαλήμ/Ἰεροσόλυμα, Hierousalḗm/Hierosóluma; hy, Երուսաղեմ, Erusałēm. i ...
, 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 The Hebrew University of Jerusalem (HUJI; he, הַאוּנִיבֶרְסִיטָה הַעִבְרִית בִּירוּשָׁלַיִם) is a public research university based in Jerusalem, Israel. Co-founded by Albert Einstein and Dr. Chaim Weiz ...
in 1953 and a
Ph.D. A Doctor of Philosophy (PhD, Ph.D., or DPhil; Latin: or ') is the most common degree at the highest academic level awarded following a course of study. PhDs are awarded for programs across the whole breadth of academic fields. Because it is a ...
from
Princeton University Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...
in 1956.


Career

Rabin became Associate Professor of Mathematics at the
University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant u ...
(1961–62) and
MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the mo ...
(1962-63). Before moving to
Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of higher le ...
as Gordon McKay Professor of Computer Science in 1981, he was a professor at the Hebrew University. In the late 1950s, he was invited for a summer to do research for IBM at the Lamb Estate in
Westchester County, New York Westchester County is located in the U.S. state of New York. It is the seventh most populous county in the State of New York and the most populous north of New York City. According to the 2020 United States Census, the county had a population o ...
with other promising mathematicians and scientists. It was there that he and
Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who 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, Ca ...
wrote the paper "Finite Automata and Their Decision Problems". Soon, using nondeterministic automata, they were able to re-prove Kleene's result that finite state machines exactly accept regular languages. As to the origins of what was to become
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...
, the next summer Rabin returned to the Lamb Estate. John McCarthy posed a puzzle to him about spies, guards, and passwords, 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 the 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 is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. 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 Forrest Moore (November 23, 1925 in Baltimore, Maryland – June 14, 2003 in Madison, Wisconsin) was an American professor of mathematics and computer science, the inventor of the Moore machine, Moore finite state machine, and an early pione ...
to work at
Bell Labs Nokia Bell Labs, originally named Bell Telephone Laboratories (1925–1984), then AT&T Bell Laboratories (1984–1996) and Bell Labs Innovations (1996–2007), is an American industrial research and scientific development company owned by mult ...
, where Rabin introduced
probabilistic automata In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the nondeterministic finite automaton; it includes the probability of a given transition into the finite state machine, transition function, turning it int ...
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 introduced infinite-tree automata and proved that the monadic second-order theory of ''n'' successors ( S2S when ''n'' = 2) is decidable. A key component of the proof implicitly showed
determinacy Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and sim ...
of
parity game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...
s, which lie in the third level of the
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 ...
. In 1975, Rabin finished his tenure as Rector of the Hebrew University of Jerusalem and went to the
Massachusetts Institute of Technology The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the ...
in the USA as a visiting professor.
Gary Miller Gary Miller may refer to: *Gary Miller (politician) (born 1948), American politician * Michael Dunn (actor) (Gary Neil Miller, 1934–1973), American actor * Gary L. Miller (1947–1969), American soldier and Medal of Honor recipient * Gary Miller ...
was also there and had his
polynomial In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
time test for primality based on the
extended 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, whic ...
. While there, Rabin invented the
Miller–Rabin primality test The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen prima ...
, a randomized algorithm that can determine very quickly (but with a tiny probability of error) whether a number is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. Rabin's method was based on previous work of
Gary Miller Gary Miller may refer to: *Gary Miller (politician) (born 1948), American politician * Michael Dunn (actor) (Gary Neil Miller, 1934–1973), American actor * Gary L. Miller (1947–1969), American soldier and Medal of Honor recipient * Gary Miller ...
that solved the problem deterministically with the assumption that the
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, whic ...
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 Martin Solovay (born December 15, 1938) is an American mathematician specializing in set theory. Biography Solovay earned his Ph.D. from the University of Chicago in 1964 under the direction of Saunders Mac Lane, with a dissertation on '' ...
, and
Volker Strassen Volker Strassen (born April 29, 1936) is a German mathematician, a professor emeritus in the department of mathematics and statistics at the University of Konstanz. For important contributions to the analysis of algorithms he has received many aw ...
were given the
Paris Kanellakis Award The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery (ACM) to honor "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing". It wa ...
for their work on primality testing. In 1976 he was invited by Joseph Traub to meet at
Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
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 The Rabin cryptosystem is a family of public-key encryption schemes based on a trapdoor function whose security, like that of RSA, is related to the difficulty of integer factorization. The Rabin trapdoor function has the advantage that invertin ...
, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of
integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...
. In 1981, Rabin reinvented a weak variant of the technique of oblivious transfer 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 Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing A ...
, created one of the most well-known efficient
string search algorithm In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string ...
s, the Rabin–Karp string search algorithm, known for its
rolling hash A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input. A few hash functions allow a rolling hash to be computed very quickly—the new hash value ...
. Rabin's more recent research has concentrated on computer security. He is currently the
Thomas J. Watson Sr. Thomas John Watson Sr. (February 17, 1874 – June 19, 1956) was an American businessman who served as the chairman and CEO of IBM. He oversaw the company's growth into an international force from 1914 to 1956. Watson developed IBM's managemen ...
Professor of Computer Science at
Harvard University Harvard University is a private Ivy League research university in Cambridge, Massachusetts. Founded in 1636 as Harvard College and named for its first benefactor, the Puritan clergyman John Harvard, it is the oldest institution of higher le ...
and Professor of Computer Science at
Hebrew University The Hebrew University of Jerusalem (HUJI; he, הַאוּנִיבֶרְסִיטָה הַעִבְרִית בִּירוּשָׁלַיִם) is a public research university based in Jerusalem, Israel. Co-founded by Albert Einstein and Dr. Chaim Weiz ...
. During the spring semester of 2007, he was a visiting professor at
Columbia University Columbia University (also known as Columbia, and officially as Columbia University in the City of New York) is a private research university in New York City. Established in 1754 as King's College on the grounds of Trinity Church in Manhatt ...
teaching ''Introduction to
Cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
''.


Awards and honours

Rabin is a foreign member of the
United States National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nati ...
, a member of the
American Philosophical Society The American Philosophical Society (APS), founded in 1743 in Philadelphia, is a scholarly organization that promotes knowledge in the sciences and humanities through research, professional meetings, publications, library resources, and communit ...
, a member of the
American Academy of Arts and Sciences The American Academy of Arts and Sciences (abbreviation: AAA&S) is one of the oldest learned societies in the United States. It was founded in 1780 during the American Revolution by John Adams, John Hancock, James Bowdoin, Andrew Oliver, and ...
, a member of the
French Academy of Sciences The French Academy of Sciences (French: ''Académie des sciences'') is a learned society, founded in 1666 by Louis XIV of France, Louis XIV at the suggestion of Jean-Baptiste Colbert, to encourage and protect the spirit of French Scientific me ...
, and a foreign member of the
Royal Society The Royal Society, formally The Royal Society of London for Improving Natural Knowledge, is a learned society and the United Kingdom's national academy of sciences. The society fulfils a number of roles: promoting science and its benefits, re ...
. In 1976, the
Turing Award The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery (ACM) for contributions of lasting and major technical importance to computer science. It is generally recognized as the highest distinction in compu ...
was awarded jointly to Rabin and
Dana Scott Dana Stewart Scott (born October 11, 1932) is an American logician who 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, Ca ...
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) classic paper has been a continuous source of inspiration for subsequent work in this field.''
In 1995, Rabin was awarded the
Israel Prize The Israel Prize ( he, פרס ישראל; ''pras israél'') is an award bestowed by the State of Israel, and regarded as the state's highest cultural honor. History The Israel Prize is awarded annually, on Israeli Independence Day, in a state cer ...
, in computer sciences. In 2010, Rabin was awarded the
Tel Aviv University Tel Aviv University (TAU) ( he, אוּנִיבֶרְסִיטַת תֵּל אָבִיב, ''Universitat Tel Aviv'') is a public research university in Tel Aviv, Israel. With over 30,000 students, it is the largest university in the country. Locate ...
Dan David Prize The Dan David Prize is a major international award that recognizes and supports outstanding contributions to the study of history and other disciplines that shed light on the human past. It awards nine prizes of $300,000 each year to outstanding ...
("Future" category), jointly with
Leonard Kleinrock Leonard Kleinrock (born June 13, 1934) is an American computer scientist and a long-tenured professor at UCLA's Henry Samueli School of Engineering and Applied Science. In the early 1960s, Kleinrock pioneered the application of queueing theory ...
and
Gordon E. Moore Gordon Earle Moore (born January 3, 1929) is an American businessman, engineer, and the co-founder and chairman emeritus of Intel Corporation. He is also the original proponent of Moore's law. As of March 2021, Moore's net worth is report ...
, for Computers and Telecommunications. Rabin was awarded an Honorary Doctor of Science from Harvard University in 2017.


Personal life

Rabin has as a daughter computer scientist
Tal Rabin Tal Rabin (Hebrew: טל רבין, born 1962) is a computer scientist and Professor of Computer and Information Science at the University of Pennsylvania. She was previously the head of Research at the Algorand Foundation and the head of the cr ...
.


See also

* Oblivious transfer *
Rabin automaton Rabin is a Hebrew surname. It originates from the Hebrew word ''rav'' meaning Rabbi, or from the name of the specific Rabbi Abin. The most well known bearer of the name was Yitzhak Rabin, prime minister of Israel and Nobel Peace prize Laureate. ...
*
Rabin fingerprint The Rabin fingerprinting scheme is a method for implementing fingerprints using polynomials over a finite field. It was proposed by Michael O. Rabin. Scheme Given an ''n''-bit message ''m''0,...,''m''n-1, we view it as a polynomial of degree ''n''- ...
*
Hyper-encryption Hyper-encryption is a form of encryption invented by Michael O. Rabin which uses a high-bandwidth source of public random bits, together with a secret key that is shared by only the sender and recipient(s) of the message. It uses the assumptions of ...
*
List of Israel Prize recipients This is a complete list of recipients of the Israel Prize from the inception of the Prize in 1953 through to 2022. List For each year, the recipients are, in most instances, listed in the order in which they appear on the official Israel Prize ...


References


External links


Short Description in an Information Science Hall of Fame at University of Pittsburgh


* ttp://www.eecs.harvard.edu/~cat/rabinisms.html 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 Jay Lipton (born September 6, 1946) is an Americans, American computer scientist who is Associate Dean of Research, Professor, and the Frederick G. Storey Chair in Computing in the College of Computing at the Georgia Institute of Technolo ...
{{DEFAULTSORT:Rabin, Michael O. 1931 births Foreign associates of the National Academy of Sciences Israeli mathematicians Israeli computer scientists Hebrew Reali School alumni Einstein Institute of Mathematics alumni Hebrew University of Jerusalem faculty Columbia University faculty Turing Award laureates Dijkstra Prize laureates Israel Prize in computer sciences recipients Members of the Israel Academy of Sciences and Humanities Modern cryptographers Logicians Theoretical computer scientists Living people Foreign Members of the Royal Society Tarski lecturers International Association for Cryptologic Research fellows IBM Research computer scientists IBM employees Harvard University faculty ETH Zurich faculty Gödel Lecturers Members of the American Philosophical Society