EXPERIENCE:
Professor, Harvard (Gordon McKay Professor of Computer Science,1981-1983; Thomas J. Watson Sr. Professor of Computer Science 1983); Professor, Hebrew University of Jerusalem (Albert Einstein Chair,1980-1999; Pro-Rector, 1976-1980); Rector (Academic Head) 1972-1975; Chairman, Computer Science Department 1970-1971; Chairman, Institute of Mathematics 1964-1966; Senior Lecturer, Associate Professor and Professor 1958-1965); Institute for Advanced Study, Princeton (1958 Member; H. B. Fine Instructor1956-1958). He has also held many different visiting appointments at major universities in Europe and the United States.
HONORS AND AWARDS:
C. Weizmann Prize for Exact Sciences (1960); Best Teacher Award, Courant Institute of Mathematics (1970); Rothschild Prize in Mathematics (1974); Member American Academy of Arts and Sciences (1975); ACM Turing Award (1976); Harvey Prize in Science and Technology (1980); Israel Academy of Sciences and Humanities (1982); Foreign Associate US National Academy of Science (1984); Foreign Member American Philosophical Society (1988); President, Division for Logic, Methodology, and Philosophy of Science, IUHPS (1990-2003); Israel Prize in Exact Sciences/Computer Science (1995); Associé Étranger, French Academy of Sciences (1995); Honorary Doctorate, University of Bordeaux I (1996); Honorary Doctorate, Haifa University (1996); Honorary Doctorate, New York University (1998); Honorary Doctorate, Israel Open University Honorary Fellow (1999); IEEE Charles Babbage Award in Computer Science (2000); Honorary Doctorate, Ben-Gurion University (2000); EMET Prize in Exact Sciences/Computer Science (2004); ACM Kanellakis Theory and Pratice Award (2004); ASL Godel Award Lecture (2004); Member European Academy of Science (2007); Foreign Member Royal Society (2007); Honorary Doctorate, Wroclaw University (2007); IACR Fellow (2009); Dijkstra Prize (2015); Tel Aviv University Dan David Prize (“Future” category) jointly with Leonard Kleinrock and Gordon E. Moore, for Computers and Telecommunications.
MICHAEL O. RABIN DL Author Profile link
United States – 1976
CITATION
Along with Dana S. Scott, 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.
SHORT ANNOTATED
BIBLIOGRAPHY
ACM TURING AWARD
LECTURE
RESEARCH
SUBJECTS
VIDEO INTERVIEW
ORAL HISTORY INTERVIEW
Michael Rabin was born in 1931 in Breslau, Germany, now Wroclaw, Poland. His father, a rabbi, moved the family to Palestine in 1935. Michael was given a very good primary education and attended the best high school in Haifa.
Michael related the following story to explain how he became interested in mathematics at about the age of 10 or 11. In the hallway of his school he encountered a few older students attempting to find a proof for an elementary problem in geometry. To his delight, he was able to solve it, and he enjoyed the experience of starting with just a few known facts about a geometrical figure and deducing others that are not obvious. The idea that with thought alone one can prove geometric statements inspired him to study mathematics.
In high school he was taught mathematics by Elisha Netanyahu, the uncle of the later Israeli Prime Minister. Netanyahu was an important mathematician in his own right, and later became a professor at the Technion in Haifa and Dean of the Faculty of Science. While a high school teacher, Netanyahu organized a weekly seminar to teach topics in advanced mathematics to a select group of students. Rabin participated, and quickly learned much more than would be the norm for a student of his age.
Rabin finished high school at the age of 16. Like most of his classmates, he was then drafted into the army to fight for the independence of the then-new state of Israel. He filled the periods of inactivity by reading mathematics textbooks. One by Professor Abraham Fraenkel in Jerusalem was on set theory, and Rabin wrote to him. Fraenkel, impressed by the depth of the correspondence, met with Rabin and later was instrumental in having him mustered out of the military to attend the University of Jerusalem. He was admitted directly into a Master’s degree program to study algebra, and graduated in 1953. His thesis solved a significant open problem that had been proposed by the German mathematician Emmy Noether.
Rabin describes his time at Hebrew University and his undergraduate thesis work.
On the strength of the thesis he was admitted to a PhD program at Princeton, where he studied under Alonzo Church and graduated in 1957. After Rabin finished his PhD he was invited by IBM to attend a summer research workshop for a select group of young scientists. It was there that he and Dana Scott collaborated on the famous paper “Finite Automata and Their Decision Problem” [1] that led to their joint Turing Award in 1976.
Rabin describes his graduate studies at the University of Pennsylvania and (under Alonzo Church) at Princeton.
Automata theory had really begun with the 1943 study of artificial neural networks by Walter Pitts and Warren McCulloch. Others continued this biologically-inspired work. Rabin and Scott moved away from neural networks, and instead used a computational model known as a finite state machine. These theoretical machines, like the Turing machine, move from one state to another depending on the input and the defined transition rules. Finite state machines had been investigated before, but Rabin and Scott considered different kinds. One was a nondeterministic machine that did not just have one possible transition out of each state, but had several. Essentially the machine could, upon accepting an input symbol, replicate itself, and then each machine would proceed with the computation along one of the possible transitions. As noted in the citation for the Turing Award, this concept of a nondeterministic machine has proven to be extremely valuable in the theoretical investigation of many problems, and continues to be an inspiration for new work.
Rabin recounts the work with Dana Scott that led to their 1959 paper “Finite Automata and their Decision Problems”.
The next summer Rabin was again invited to the IBM research workshop. He met another future Turing Award recipient, John McCarthy, who explained a puzzle to him about spies and guards. The spies have passwords that allow them to pass from enemy territory to their own. The guards cannot be trusted to keep the passwords secret, so some method had to be found to verify that even if the enemy gains knowledge of the password, the spies can safely return but the enemy infiltrators are kept out. One solution came from the middle-square method, which had been proposed by mathematician John von Neumann as a way of generating random numbers. Each spy is given a 100-digit number x, and the guards are given another 100-digit number obtained by taking the middle digits from x2. When returning, the spy gives the guard x. The guard then computes x2 and compares the middle digits to the number he possesses as a pass code. Even if the guard passes his number to an enemy, it is very difficult for the enemy to determine what initial number resulted in those 100 middle digits of x2.
Rabin retells the story about guards and spies that led him to work on degrees of computational difficulty.
Rabin began thinking in general about functions that are difficult to invert —in this case computing the original number x knowing only the middle digits of x2. His study resulted in the groundbreaking paper [2] “Degree of Difficulty of Computing a Function and a Partial Ordering of Recursive Sets”, which was the starting point for his later advances in the theoretical study of computational complexity particularly in relation to cryptography.
Rabin had returned to the University of Jerusalem, first as a senior lecturer, then as Associate Professor, and then Professor. He kept up his prodigious research output while also becoming chairman of their Institute of Mathematics, chairman of the Department of Computer Science, and Rector (academic head) of the entire University.
In 1975, having finished his term at Rector, he went to MIT as a Visiting Professor and worked on primality testing with Gary Miller. This involves determining if a very large number is prime—whether the number has no divisors other than itself and 1. Miller had earlier developed a primality test that was based on the unproven Riemann hypothesis. That bothered Rabin, because if the Riemann hypothesis was eventually shown to be false it would bring into question any methods based on it. Michael had earlier worked on probabilistic automata, theoretical machines for which a random number is used to determine which transition to take from each state. While not deterministic in the sense that it always provides a provable result, if run a number of times the chance of it being incorrect can be made vanishingly small. Rabin used this concept to develop a primality testing algorithm [3] called the Miller-Rabin test. It was later shown to be deterministic: it is guaranteed to work if a certain number of tests were done.
Rabin explains the concept of probabilistic automata and his work with Gary Miller to apply it to prime testing.
Adding randomness to algorithms was to be a theme for much of Rabin’s later work on many different problems. One of his favorites, the four-square problem that had first been discussed by Joseph-Louis Lagrange in 1770, was how to express an integer as the sum of four squares: for any integer y find four not necessarily unique, integers a, b, c, d such that y = a2 + b2 + c2 + d2. Lagrange had shown that it is always possible, but nobody knew an efficient algorithm to find a, b, c and d. In speaking to a class of students at MIT in 1977 Rabin proposed a randomized algorithm, which he and Jeff Shallit later published as part of a larger study of randomized algorithms [4].
Rabin’s later work concerns cryptographic problems for preventing piracy on the internet. Recently he has been examining how to ensure the privacy and secrecy of online auctions. In auctions like those conducted by Google for advertising slots, the participants want their identity and bidding strategy to remain anonymous, but want to be assured that the results of the auction are fair. Rabin has worked as a consultant to create a zero-knowledge proof that gives such assurances.
经历：哈佛大学教授（戈登-麦肯锡教授）。
哈佛大学教授（Gordon McKay计算机科学教授，1981-1983；Thomas J. Watson Sr. 计算机科学教授，1983）。1983年）；耶路撒冷希伯来大学教授（阿尔伯特-爱因斯坦讲座，1980-1999年；副校长，1976-1980年）；校长（学术负责人）1972-1975年；计算机科学系主任1970-1971年；数学研究所主席1964-1966年；高级讲师、副教授和教授1958-1965年）；普林斯顿高等研究所（1958年成员；H. B. Fine讲师1956-1958）。他还在欧洲和美国的主要大学担任过许多不同的访问职务。
荣誉和奖项。
C. 魏茨曼精确科学奖（1960年）；库兰特数学研究所最佳教师奖（1970年）；罗斯柴尔德数学奖（1974年）；美国艺术与科学学院成员（1975年）；ACM图灵奖（1976年）；哈维科技奖（1980年）；以色列科学与人文学院（1982年）。美国国家科学院外籍院士（1984年）；美国哲学学会外籍会员（1988年）；IUHPS逻辑学、方法学和科学哲学分部主席（1990-2003年）；以色列精确科学/计算机科学奖（1995年）；法国科学院Associé Étranger（1995年）；波尔多第一大学荣誉博士（1996年）。海法大学名誉博士（1996年）；纽约大学名誉博士（1998年）；以色列开放大学名誉博士，名誉研究员（1999年）；IEEE查尔斯-巴贝奇计算机科学奖（2000年）；本古里安大学名誉博士（2000年）；EMET精确科学/计算机科学奖（2004年）。ACM卡内拉基斯理论与实践奖（2004年）；ASL戈德尔奖讲座（2004年）；欧洲科学院院士（2007年）；英国皇家学会外国会员（2007年）；弗罗茨瓦夫大学荣誉博士（2007年）；IACR研究员（2009年）；Dijkstra奖（2015年）；特拉维夫大学丹-大卫奖（"未来 "类），与Leonard Kleinrock和Gordon E. Moore联合颁发。摩尔共同设立的计算机和电信奖。
MICHAEL O. RABIN DL作者简介链接
美国 - 1976年
奖状
与Dana S. Scott共同发表论文 "有限自动机及其决策问题"，提出了非决定性机器的概念，该概念已被证明是一个非常有价值的概念。他们（斯科特和拉宾）的经典论文一直是该领域后续工作的灵感来源。
