Michael O. Rabin
Michael Oser Rabin is an Israeli mathematician and computer scientist and a recipient of the Turing Award. Rabin was born in 1931 in Breslau, the son of a rabbi. In 1935, he emigrated with his family to Mandate Palestine; as a young boy, he was interested in mathematics and his father sent him to the best high school in Haifa, where he studied under mathematician Elisha Netanyahu, a high school teacher. After high school, he was drafted into the army during the 1948 Arab–Israeli War; the mathematician Abraham Fraenkel, a professor of mathematics in Jerusalem, intervened with the army command, Rabin was discharged to study at the university in 1949. He received an M. Sc. from Hebrew University of Jerusalem in 1953 and a Ph. D. from Princeton University in 1956. Rabin became Associate Professor of Mathematics at the University of California, Berkeley and MIT. Before moving to Harvard University 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 with other promising mathematicians and scientists.
It was there that he and Dana Scott 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 accept regular languages; as to the origins of what was to become computational complexity theory, the next summer Rabin returned to the Lamb Estate. John McCarthy posed a puzzle to him about spies 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 with the description of the complexity classes P and NP. Rabin returned to Jerusalem, researching logic, working on the foundations of what would be known as computer science, he was an associate professor and the head of the Institute of Mathematics at the Hebrew University at 29 years old, a full professor by 33. Rabin recalls, "There was 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 to work at Bell Labs, 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 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 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 finished his tenure as Rector of the Hebrew University of Jerusalem and went to the Massachusetts Institute of Technology in the USA as a visiting professor. Gary Miller was there and had his polynomial time test for primality based on the extended Riemann hypothesis. While there, Rabin invented the Miller–Rabin primality test, a randomized algorithm that can determine quickly whether a number is prime.
Rabin's method was based on previous work of Gary Miller that solved the problem deterministically with the assumption that the 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, in 2003 Miller, Robert M. Solovay, Volker Strassen were given the Paris Kanellakis Award for their work on primality testing. In 1976 he was invited by Joseph Traub to meet at Carnegie Mellon University and presented the primality test. After he gave that lecture, Traub had said, "No, no, this is revolutionary, it's going to become important."In 1979, Rabin invented the Rabin cryptosystem, the first asymmetric cryptosystem whose security was proved equivalent to the intractability of integer factorization. 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, together with Richard Karp, created one of the most well-known efficient string search algorithms, the Rabin–Karp string search algorithm, known for its rolling hash. Rabin's more recent research has concentrated on computer security, he is the Thomas J. Watson Sr. Professor of Computer Science at Harvard University and Professor of Computer Science at Hebrew University. During the spring semester of 2007, he was a visiting professor at Columbia University teaching Introduction to Cryptography. Rabin is a foreign member of the United States National Academy of Sciences, a member of the French Academy of Sciences and a foreign member of the Royal Society. In 1976, the Turing Award was awarded jointly to Rabin and 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 classic paper has been a continuous source of inspiration for subsequent work in this field. In 1995, Rabin was awarded the Israel Prize, in computer sciences. In 2010, Rabin was awarded the Tel Aviv University
Grenoble is a city in southeastern France, at the foot of the French Alps where the river Drac joins the Isère. Located in the Auvergne-Rhône-Alpes region, Grenoble is the capital of the department of Isère and is an important European scientific centre; the city advertises itself as the "Capital of the Alps", due to its size and its proximity to the mountains. Grenoble's history goes back to a time when it was a small Gallic village, it gained somewhat in stature by becoming the capital of the Dauphiné in the 11th century, but Grenoble remained for most of its history a modest parliamentary and garrison city on the borders of the kingdom of France. Industrial development increased the prominence of Grenoble through several periods of economic expansion over the last three centuries; this started with a booming glove industry in the 18th and 19th centuries, continued with the development of a strong hydropower industry in the late 19th to early 20th centuries, ended with a post-World War II economic boom symbolized by the holding of the X Olympic Winter Games in 1968.
The city has grown to be one of Europe's most important research and innovation centers, with each fifth inhabitant working directly in these domains. The population of the city of Grenoble was 160,215 at the 2013 census, while the population of the Grenoble metropolitan area was 664,832; the residents of the city are called "Grenoblois". The many suburb communes that make up the rest of the metropolitan area include three with populations exceeding 20,000: Saint-Martin-d'Hères, Échirolles, Fontaine. For the ecclesiastical history, see Bishopric of Grenoble; the first references to what is now Grenoble date back to 43 BC. Cularo was at that time a small Gallic village of the Allobroges tribe, near a bridge across the Isère. Three centuries and with insecurity rising in the late Roman empire, a strong wall was built around the small town in 286 AD; the Emperor Gratian visited Cularo and, touched by the people's welcome, made the village a Roman city. In honour of this, Cularo was renamed Gratianopolis in 381.
Christianity spread to the region during the 4th century, the diocese of Grenoble was founded in 377 AD. From that time on, the bishops exercised significant political power over the city; until the French Revolution, they styled themselves the "bishops and princes of Grenoble". After the collapse of the Roman Empire, the city was part of the first Burgundian kingdom in the 5th century and the second Burgundian Kingdom of Arles until 1032, when it was integrated into the Holy Roman Empire. Arletian rule was interrupted between 970 due to Arab rule based in Fraxinet. Grenoble grew in the 11th century when the Counts of Albon chose the city as the capital of their territories. At the time, their possessions were a patchwork of several territories sprawled across the region; the central position of Grenoble allowed the Counts to strengthen their authority. When they took the title of "Dauphins", Grenoble became the capital of the State of Dauphiné. Despite their status, the Counts had to share authority over the city with the Bishop of Grenoble.
One of the most famous of those was Saint Hugh. Under his rule, the city's bridge was rebuilt, a regular and leper hospital were built; the inhabitants of Grenoble took advantage of the conflicts between the Counts and the bishops and obtained the recognition of a Charter of Customs that guaranteed their rights. That charter was confirmed by Kings Louis XI in 1447 and Francis I in 1541. In 1336 the last Dauphin Humbert II founded a court of justice, the Conseil delphinal, which settled at Grenoble in 1340, he established the University of Grenoble in 1339. Without an heir, Humbert sold his state to France in 1349, on the condition that the heir to the French crown used the title of Dauphin; the first one, the future Charles V, spent nine months in Grenoble. The city remained the capital of the Dauphiné, henceforth a province of France, the Estates of Dauphiné were created; the only Dauphin who governed his province was the future Louis XI, whose "reign" lasted from 1447 to 1456. It was only under his rule.
The Old Conseil Delphinal became a Parlement, strengthening the status of Grenoble as a Provincial capital. He ordered the construction of the Palais du Parlement and ensured that the Bishop pledged allegiance, thus forging the political union of the city. At that time, Grenoble was a crossroads between Vienne, Geneva and Savoy, it was the industrial centre of the Dauphiné and the biggest city of the province, but nonetheless a rather small one. Owing to Grenoble's geographical situation, French troops were garrisoned in the city and its region during the Italian Wars. Charles VIII, Louis XII, Francis I went several times to Grenoble, its people had to suffer from the exactions of the soldiers. The nobility of the region took part in doing so gained significant prestige; the best-known of its members was Bayard, "the knight without fear and beyond reproach". Grenoble suffered as a result of the French Wars of Religion; the Dauphiné was indeed an important settlement for Protestants and therefore experienced several conflicts.
The baron des Adrets, the leader of the Huguenots, pillaged the Cathedral of Grenoble and destroyed the tombs of the former Dauphins. In August 1575, Lesdiguières became the new leader of the Protestants and, thanks to the accession of Henry
I Kathimerini is a daily morning newspaper published in Athens. Its first edition was printed on September 15, 1919, it is published in the Greek language, as well as in an abridged English-language edition. The English edition is sold separately in the United States and as a supplement to the international edition of The New York Times in Greece and Cyprus, is available online. On November 2008 a Kathimerini Cypriot weekend edition began to circulate. Kathimerini is affiliated with the weekly newspaper Athens Plus published by I Kathimerini S. A. and the International Herald Tribune. Kathimerini was founded by Georgios Vlachos in 1919 and was inherited by his daughter Helen Vlachos and her husband, retired submarine commander Constantine Loundras. Considered a high-quality broadsheet, Kathimerini is traditionally perceived as one of the main conservative voices of Greek media; the newspaper was critical of Eleftherios Venizelos in the early 20th century, opposed the Papandreou family in the postwar years.
It maintains a traditional layout, with its original griffin logo, incorporates illustrated glossy inserts in its Sunday edition. Vlachos sold the company shortly before her death in October 1995 to Aristeidis Alafouzos, a real estate developer and shipping magnate, who died in 2017. There is no data on Kathimerini's daily edition circulation, since the newspaper has prohibited press agencies to release such data, its Sunday edition had a circulation of 95,007 in January 2014. According to third-party web analytics providers Alexa and SimilarWeb, Kathimerini's website is the 81th and 86th most visited in Greece as of August 2015. SimilarWeb rates the site as the 23rd most visited news website in Greece, attracting over 3 million visitors per month. Editor-in-chief – Andreas Paraschos Managing editor – Alexis Papahelas Kathimerini is published by Kathimerini Publishing SA; this company was listed on the Athens Stock Exchange but it was delisted on December 2015. Official website Kathimerini English Edition Website Kathimerini Cypriot Edition Website
Sir Maurice Vincent Wilkes was a British computer scientist who designed and helped build the Electronic delay storage automatic calculator, one of the earliest stored program computers and invented microprogramming, a method for using stored-program logic to operate the control unit of a central processing unit's circuits. At the time of his death, Wilkes was an Emeritus Professor of the University of Cambridge. Wilkes was born in Dudley, Worcestershire and grew up in Stourbridge, West Midlands, where his father worked on the estate of the Earl of Dudley, he was educated at King Edward VI College and during his school years he was introduced to amateur radio by his chemistry teacher. He went on to read the Mathematical Tripos at St John's College, Cambridge from 1931–34, continuing to complete a PhD in physics on the topic of radio propagation of long radio waves in the ionosphere in 1936, he was appointed to a junior faculty position of the University of Cambridge through which he was involved in the establishment of a computing laboratory.
He was called up for military service during World War II and worked on radar at the Telecommunications Research Establishment, in operational research. In 1945, Wilkes was appointed as the second director of the University of Cambridge Mathematical Laboratory; the Cambridge laboratory had many different computing devices, including a differential analyser. One day Leslie Comrie visited Wilkes and lent him a copy of John von Neumann's prepress description of the EDVAC, a successor to the ENIAC under construction by Presper Eckert and John Mauchly at the Moore School of Electrical Engineering, he had to read it overnight. He decided that the document described the logical design of future computing machines, that he wanted to be involved in the design and construction of such machines. In August 1946 Wilkes travelled by ship to the United States to enroll in the Moore School Lectures, of which he was only able to attend the final two weeks because of various travel delays. During the five-day return voyage to England, Wilkes sketched out in some detail the logical structure of the machine which would become EDSAC.
Since his laboratory had its own funding, he was able to start work on a small practical machine, the Electronic Delay Storage Automatic Calculator, once back at Cambridge. He decided that his mandate was not to invent a better computer, but to make one available to the university. Therefore, his approach was relentlessly practical, he used only proven methods for constructing each part of the computer. The resulting computer was smaller than other planned contemporary computers. However, his laboratory's computer was the second practical stored program computer to be completed, operated from May 1949, well over a year before the much larger and more complex EDVAC. In 1950, along with David Wheeler, Wilkes used EDSAC to solve a differential equation relating to gene frequencies in a paper by Ronald Fisher; this represents the first use of a computer for a problem in the field of biology. In 1951, he developed the concept of microprogramming from the realisation that the central processing unit of a computer could be controlled by a miniature specialised computer program in high-speed ROM.
This concept simplified CPU development. Microprogramming was first described at the University of Manchester Computer Inaugural Conference in 1951 published in expanded form in IEEE Spectrum in 1955; this concept was implemented for the first time in EDSAC 2, which used multiple identical "bit slices" to simplify design. Interchangeable, replaceable tube assemblies were used for each bit of the processor; the next computer for his laboratory was the Titan, a joint venture with Ferranti Ltd begun in 1963. It supported the UK's first time-sharing system and provided wider access to computing resources in the university, including time-shared graphics systems for mechanical CAD.. Control Memory, used in today's computer was developed by using the concept of this Microprogramming. A notable design feature of the Titan's operating system was that it provided controlled access based on the identity of the program, as well as or instead of, the identity of the user, it introduced the password encryption system used by Unix.
Its programming system had an early version control system. Wilkes is credited with the idea of symbolic labels and subroutine libraries; these are fundamental developments that made programming much easier and paved the way for high-level programming languages. Wilkes worked on an early timesharing systems and distributed computing. Toward the end of the 1960s, Wilkes became interested in capability-based computing, the laboratory assembled a unique computer, the Cambridge CAP. In 1974 Wilkes encountered a Swiss data network that used a ring topology to allocate time on the network; the laboratory used a prototype to share peripherals. Commercial partnerships were formed, similar technology became available in England, he received a number of distinctions: he was a knight bachelor, Distinguished Fellow of the British Computer Society, a Fellow of the Royal Academy of Engineering and a Fellow of the Royal Society. Wilkes received a number of distinctions: he was a knight bachelor, Distinguished Fellow of the British Computer Society, a Fellow of the Royal Academy of Engineering and was elected a Fellow of the Royal Society in 1956.
He was a founder member of the British Computer
Edmund M. Clarke
Edmund Melson Clarke, Jr. is an American retired computer scientist and academic noted for developing model checking, a method for formally verifying hardware and software designs. He is the FORE Systems Professor of Computer Science at Carnegie Mellon University. Clarke, along with E. Allen Emerson and Joseph Sifakis, is a recipient of the 2007 Association for Computing Machinery A. M. Turing Award. Clarke received a B. A. degree in mathematics from the University of Virginia, Charlottesville, VA, in 1967, an M. A. degree in mathematics from Duke University, Durham NC, in 1968, a Ph. D. degree in Computer Science from Cornell University, Ithaca NY in 1976. After receiving his Ph. D. he taught in the Department of Computer Science at Duke University, for two years. In 1978 he moved to Harvard University, Cambridge, MA where he was an Assistant Professor of Computer Science in the Division of Applied Sciences, he left Harvard in 1982 to join the faculty in the Computer Science Department at Carnegie Mellon University, Pittsburgh, PA.
He was appointed Full Professor in 1989. In 1995 he became the first recipient of the FORE Systems Professorship, an endowed chair in the Carnegie Mellon School of Computer Science. Clarke's interests include hardware verification and automatic theorem proving. In his Ph. D. thesis he proved that certain programming language control structures did not have good Hoare style proof systems. In 1981 he and his Ph. D. student E. Allen Emerson first proposed the use of model checking as a verification technique for finite state concurrent systems, his research group pioneered the use of model checking for hardware verification. Symbolic model checking using BDDs was developed by his group; this important technique was the subject of Kenneth McMillan's Ph. D. thesis, which received an ACM Doctoral Dissertation Award. In addition, his research group developed the first parallel resolution theorem prover and the first theorem prover to be based on a symbolic computation system. In 2009, he led the creation of the Computational Modeling and Analysis of Complex Systems center, funded by the National Science Foundation.
This center has a team of researchers, spanning multiple universities, applying abstract interpretation and model checking to biological and embedded systems. Clarke is a fellow of the ACM and the IEEE, he received a Technical Excellence Award from the Semiconductor Research Corporation in 1995 and an Allen Newell Award for Excellence in Research from the Carnegie Mellon Computer Science Department in 1999. He was a co-winner along with Randal Bryant, E. Allen Emerson, Kenneth McMillan of the ACM Paris Kanellakis Award in 1999 for the development of symbolic model checking. In 2004 he received the IEEE Computer Society Harry H. Goode Memorial Award for significant and pioneering contributions to formal verification of hardware and software systems, for the profound impact these contributions have had on the electronics industry, he was elected to the National Academy of Engineering in 2005 for contributions to the formal verification of hardware and software correctness. He was elected to the American Academy of Arts and Sciences in 2011.
He received the Herbrand Award in 2008 in "recognition of his role in the invention of model checking and his sustained leadership in the area for more than two decades." He received the 2014 Bower Award and Prize for Achievement in Science from the Franklin Institute for "his leading role in the conception and development of techniques for automatically verifying the correctness of a broad array of computer systems, including those found in transportation and medicine." He is a member of Phi Beta Kappa. List of pioneers in computer science Edmund M. Clarke at the Mathematics Genealogy Project Home page at Carnegie Mellon University Turing Award announcement Model Checking book CMACS home page List of publications from Microsoft Academic
The ACM A. M. Turing Award is an annual prize given by the Association for Computing Machinery to an individual selected for contributions "of lasting and major technical importance to the computer field"; the Turing Award is recognized as the highest distinction in computer science and the "Nobel Prize of computing". The award is named after Alan Turing, a British mathematician and reader in mathematics at the University of Manchester. Turing is credited as being the key founder of theoretical computer science and artificial intelligence. From 2007 to 2013, the award was accompanied by an additional prize of US $250,000, with financial support provided by Intel and Google. Since 2014, the award has been accompanied by a prize of US $1 million, with financial support provided by Google; the first recipient, in 1966, was Alan Perlis, of Carnegie Mellon University. The first female recipient was Frances E. Allen of IBM in 2006. List of ACM Awards List of science and technology awards List of prizes named after people IEEE John von Neumann Medal List of Turing Award laureates by university affiliation Turing Lecture Nobel Prize Schock Prize Nevanlinna Prize Kanellakis Award Millennium Technology Prize ACM Chronological listing of Turing Laureates Visualizing Turing Award Laureates ACM A.
M. Turing Award Centenary Celebration ACM A. M. Turing Award Laureate Interviews Celebration of 50 Years of the ACM A. M. Turing Award ACM A. M. Turing Award by SFBayACM
Donald Ervin Knuth is an American computer scientist and professor emeritus at Stanford University. He is the author of the multi-volume work The Art of Computer Programming, he contributed to the development of the rigorous analysis of the computational complexity of algorithms and systematized formal mathematical techniques for it. In the process he popularized the asymptotic notation. In addition to fundamental contributions in several branches of theoretical computer science, Knuth is the creator of the TeX computer typesetting system, the related METAFONT font definition language and rendering system, the Computer Modern family of typefaces; as a writer and scholar, Knuth created the WEB and CWEB computer programming systems designed to encourage and facilitate literate programming, designed the MIX/MMIX instruction set architectures. Knuth opposes granting software patents, having expressed his opinion to the United States Patent and Trademark Office and European Patent Organisation. Knuth was born in Milwaukee, Wisconsin, to German-Americans Ervin Henry Knuth and Louise Marie Bohning.
His father had two jobs: running a small printing company and teaching bookkeeping at Milwaukee Lutheran High School. Donald, a student at Milwaukee Lutheran High School, received academic accolades there because of the ingenious ways that he thought of solving problems. For example, in eighth grade, he entered a contest to find the number of words that the letters in "Ziegler's Giant Bar" could be rearranged to create. Although the judges only had 2,500 words on their list, Donald found 4,500 words, winning the contest; as prizes, the school received a new television and enough candy bars for all of his schoolmates to eat. In 1956, Knuth received a scholarship to the Case Institute of Technology in Ohio, he joined Beta Nu Chapter of the Theta Chi fraternity. While studying physics at the Case Institute of Technology, Knuth was introduced to the IBM 650, one of the early mainframes. After reading the computer's manual, Knuth decided to rewrite the assembly and compiler code for the machine used in his school, because he believed he could do it better.
In 1958, Knuth created a program to help his school's basketball team win their games. He assigned "values" to players in order to gauge their probability of getting points, a novel approach that Newsweek and CBS Evening News reported on. Knuth was one of the founding editors of the Engineering and Science Review, which won a national award as best technical magazine in 1959, he switched from physics to mathematics, in 1960 he received his bachelor of science degree being given a master of science degree by a special award of the faculty who considered his work exceptionally outstanding. In 1963, with mathematician Marshall Hall as his adviser, he earned a PhD in mathematics from the California Institute of Technology. After receiving his PhD, Knuth joined Caltech's faculty as an assistant professor, he accepted a commission to write a book on computer programming language compilers. While working on this project, Knuth decided that he could not adequately treat the topic without first developing a fundamental theory of computer programming, which became The Art of Computer Programming.
He planned to publish this as a single book. As Knuth developed his outline for the book, he concluded that he required six volumes, seven, to cover the subject, he published the first volume in 1968. Just before publishing the first volume of The Art of Computer Programming, Knuth left Caltech to accept employment with the Institute for Defense Analyses' Communications Research Division situated on the Princeton University campus, performing mathematical research in cryptography to support the National Security Agency. Knuth left this position to join the Stanford University faculty, where he is now Fletcher Jones Professor of Computer Science, Emeritus. Knuth is a writer, as well as a computer scientist. Knuth has been called the "father of the analysis of algorithms". In the 1970s, Knuth described computer science as "a new field with no real identity, and the standard of available publications was not that high. A lot of the papers coming out were quite wrong.... So one of my motivations was to put straight a story, badly told."
By 2011, the first three volumes and part one of volume four of his series had been published. Concrete Mathematics: A Foundation for Computer Science 2nd ed. which originated with an expansion of the mathematical preliminaries section of Volume 1 of TAoCP, has been published. Bill Gates has praised the difficulty of the subject matter in The Art of Computer Programming, stating, "If you think you're a good programmer... You should send me a résumé if you can read the whole thing." Knuth is the author of Surreal Numbers, a mathematical novelette on John Conway's set theory construction of an alternate system of numbers. Instead of explaining the subject, the book seeks to show the development of the mathematics. Knuth wanted the book to prepare students for doing creative research. In 1995, Knuth wrote the foreword to the book A=B by Marko Petkovšek, Herbert Wilf and Doron Zeilberger. Knuth is an occasional contributor of language puzzles to Word Ways: The Journal of Recreational Linguistics. Knuth has delved into recreational mathematics.
He contributed articles to the Journal of Recreational Mathematics beginning in the 1960s, was acknowledged as a major contributor in Joseph Madachy's Mathematics on Vacation. Knuth has appeared in a number of Numberphile and Computerphile videos on YouTube where he has discussed topics f