Born: 26 March 1962 in Jammu, Jammu and Kashmir, India

Died: 5 June 2009 in Atherton, San Mateo County, California, USA

Rajeev Motwani's father, Hotchand Motwani, was a Lieutenant Colonel in the Indian army. His mother was Namita Sushila and he had two brothers Sanjeev and Suneev. His father's job meant that the family moved from place to place as Rajeev was growing up, never spending more than two years in any one place. However, education was important to the Motwani family and Rajeev always attended the best missionary school in the town in which they were living. Prabhakar Raghavan writes of Rajeev's love of reading when he was a child [5]:-

Those who knew Rajeev as a young boy remember him as an avid reader. When Rajeev was seven, his father was stationed in the scenic town of Devlali near Mumbai, India. His family would walk a kilometer to the local library to get books, and the seven-year-old Rajeev would be seen reading the books they had borrowed from the library as they walked home! His brothers recall that not a single day would pass when he did not read a whole book. Rajeev would read books of all types, including novels, comics, autobiographies and scientific books.

In 1974, when Rajeev was twelve years old, the family settled down in New Delhi. His father wanted the best possible education for his sons so Rajeev sat the entrance examinations to the prestigious St Columba's High School. The principal, Brother J N Foley, was so impressed with Rajeev's performance, particularly in mathematics, that he admitted all three Motwani boys to the High School. Motwani explained where his love of mathematics came from in an interview [4]:-

This was partly shaped by the books I had at home. My parents for some reason had a lot of these books - 10 great scientists or five famous mathematicians - their life story and so on. As a child, whatever heroes you read about you want to become.

One of his fellow students at the High School wrote about Motwani [9]:-

Rajeev and I were classmates is St Columba's High School in New Delhi over 30 years ago. Of course he was a brilliant maths whiz even back then, but what struck me the most is how vividly I remember how much he used to help me and other classmates understand the complex problems that were a bit beyond our grasp.

He did not graduate from St Columba's High School but in 1978, one year before completing the course, he sat the entrance examinations for the Indian Institutes of Technology. He had wanted to study mathematics and become a mathematician but his parents had persuaded him that there was no money in mathematics but he should go into the new area of computer science. The Indian Institute of Technology in Kanpur, had been established in 1959, and was the first in India to offer courses in Computer Science. The first such courses were established in the Electrical Engineering department in 1963 and, in 1971, it began teaching a programme of Computer Science and Engineering leading to a Master's degree, the M.Tech. Motwani began studying for his B.Tech. in Computer Science and Engineering in 1978. He was taught programming by Kesav Nori who was a great influence on him [8]:-

Nori had just come back from Europe. He stayed for a year or so and taught the first course in programming. He was a wonderful teacher and used to tell great stories. ... Nori ... was a very inspiring person. He did more than just teaching. He created such a wonderful ecosystem and developed a personal connection with his students.

Motwani enjoyed himself at the Indian Institute of Technology. He had been sad not to be studying mathematics but this changed to happiness when he realised that mathematics featured in most things he was studying. He also enjoyed himself socially, playing bridge, playing volleyball, and partying with friends. He also read large numbers of science-fiction books and spent hours solving crossword puzzles. He graduated with a B.Tech. in 1983 and was offered a scholarship by the University of California at Berkley to read for a Ph.D. His thesis advisor at Berkeley was Richard Karp. He explained in [8] that he did not work at first:-

[Berkley] was a very politically oriented university. .... Ronald Reagan was the president then. So then for 3 years I had a blast. Did not do any work and fully enjoyed the environment. My advisor was Richard Karp, who won the Turing award - which is like the Nobel Prize in computer science in1985-86, when I had finished those 3 years. It was then that I thought that I was not doing anything and letting this man down. So from then on I worked really hard and was quite productive for the next two years.

Motwani was awarded a Ph.D. in 1988 by Berkeley for his thesis Probabilistic Analysis of Matching and network flow Algorithms. Donald Knuth visited Berkeley around the time that Motwani was completing his thesis. After taking advice from Richard Karp, Knuth offered Motwani a one-year position at Stanford University. Motwani accepted and began teaching at Stanford in the autumn of 1988. Seffi Naor writes [9]:-

I first met Rajeev when I came to Stanford in 1988. We were both young researchers and Rajeev struck me from the beginning as brilliant, very knowledgeable, and having broad interests. Working with him, he was always full of new ideas, prolific, but also very calm and mature. He was very ambitious of course, yet I never felt that he was in any way competitive. He had a very quiet self confidence which reflected on everyone around him. I felt very fortunate to have collaborated with him.

Soon after arriving in Stanford, Motwani met Asha Jadeja who had moved to the San Francisco Bay area after graduating from the University of Southern California. They were married on 22 March 1990 in Delhi; they had two daughters Naitri and Anya. Motwani was happy at Stanford and the University was very pleased with his work during the year, so when they offered him a permanent position he was happy to accept. His papers which were published in these early years and were reviewed in Mathematical Reviews, include the following multi-authored works: Deferred data structuring (1988); Covering orthogonal polygons with star polygons: the perfect graph approach (1988); Perfect graphs and orthogonally convex covers (1989); and A linear time approach to the set maxima problem (1992). In 1995, in collaboration with Prabhakar Raghavan, he published the book Randomized algorithms. Mark Jerrum reviewed the book:-

That there might be profit in extending the classical notion of computation to encompass random choice was a fundamental insight. The potential value of this extension became apparent in the mid-1970s with the discovery, by Rabin, and Solovay and Strassen, of fast primality tests based on the construction of "dense witnesses" to compositeness. It is only in the last decade or so, however, that most of us have come to appreciate the true importance of the role of randomness in the study of computation. Today, it seems that randomness has contributed at least as much to computer science - surprising results, exciting new techniques, and practical algorithms - as that other extension to classical computation, namely, parallelism. But whereas there have been several books on parallel computation (though fewer good ones), Motwani and Raghavan's is the first textbook, to the best of the reviewer's knowledge, devoted to randomised algorithms. The new book arrives at a strategic moment, for it is still just possible to cover in a single volume all the main aspects of the topic. ... Even though the pace is often rapid, the authors have succeeded in making the material accessible. By emphasising the role of a number of key ideas and techniques, they have elucidated the structure of the subject matter and imparted a satisfactory shape to the book. ... This is an authoritative work by researchers active in the field. The book is welcome as a reference work, as a source book for algorithmic ideas, and as a graduate-level course text. (My guess is that the material is too advanced for any but the most exceptional undergraduate class.)

John Hopcroft and Jeff Ullman published their classic book Introduction to Automata Theory, Languages, and Computation in 1979. Motwani used this book in courses he taught at Stanford and he had made such excellent contributions to the areas that he was invited to join the two original authors in a rewritten second edition of the book. This appeared in 2000 with a third edition of the now three-author work appearing in 2006.

Motwani was an inspiring lecturer. Here are some quotes from [9] by people who attended his lectures. Aleksandra Korolova writes:-

At the time when I started graduate school, I was somewhat unexcited about theoretical Computer Science, and it was Rajeev's Randomized Algorithms class that made me fall in love with theory again. His lectures were so perfectly crafted, from the progression of describing a simple approach providing the intuition to generalizing it, to doing an impeccable formal analysis, to the perfect board technique, that I left every lecture excited about a new powerful topic that I have just learned and understood. Rajeev could be covering the contents of a few serious research papers in one lecture but in his presentation, understanding them was both effortless and insightful.

Neha Kumar writes:-

As a researcher and technologist, Rajeev was brilliant - words could do little justice in describing his immense influence. As a teacher, he was awe-inspiring - carrying with him an equanimity and cheerfulness that remained undisturbed through every lecture. As a student advisor, he was kind and supportive - never impatient or proud (though he may have had every reason to be so). As a supervisor, he was trusting and understanding. Most of all, however, his immense stature never came in the way of his friendly, smiling disposition ...

In [5] Motwani's research contributions are detailed:-

Rajeev Motwani's great interest in fundamental problems of theoretical computer science and a keen interest and awareness of applications sets him apart as a rarity among theoretical computer scientists. He repeatedly exhibited a grasp of issues affecting many areas of computing, and actively sought out and influenced new applications of his theoretical ideas.

In this article his research is looked at in detail. We give here the section headings under which his research is discussed: Algorithmic combinatorics and graph theory; Probabilistically Checkable Proofs; Approximation algorithms; Randomized geometric algorithms; Data mining and information retrieval; Similarity search; and Streaming algorithms.

Perhaps Motwani is most famous for the contributions he made to developing the search engine Google. He described in detail in [8] how this came about. We give a short extract:-

We formed this research group called Midas which stood for Mining Data At Stanford. We did a lot of good work on data mining. Then there was this guy called Larry Page who wasn't really a part of the Midas group but was a friend of Sergey Brin [who was part of the group] and would show up for these meetings. He was working on this very cool idea of doing random walks on the web. When I understood what the World Wide Web would look like, I knew I had to somehow force randomness into it. When Larry showed us what he was doing, it was like a complete epiphany, we thought it was absolutely the right thing to do. So Sergey got involved and it became a sub group inside Midas. I was really a good sounding board for Sergey and Larry and I could relate to what they were doing through randomness.

Motwani, together with Sergey Brin, Larry Page and Terry Winograd, published the paper The PageRank Citation Ranking: Bringing Order to the Web in 1998. They explained in the paper:-

In this paper, we take advantage of the link structure of the Web to produce a global "importance" ranking of every web page. This ranking, called PageRank, helps search engines and users quickly make sense of the vast heterogeneity of the World Wide Web.

Also in 1998, the same four authors published the paper What Can You Do With A Web In Your Pocket. In it they announce that they have developed Google:-

We have developed a global ranking of web pages called PageRank based on the link structure of the web that has properties that are useful for search and navigation ... We have used PageRank to develop a novel search engine called Google, which also makes heavy use of anchor text.

Google was certainly not the only highly successful startup that Motwani assisted, with his technical skills, with his encouragement, and often with his financial support.

Motwani died in a tragic drowning accident in the swimming pool at his home. He was 47 years old and at the height of his career. Motwani received many honours for his outstanding contribution and it is clear that, but for his premature death, he would have received many more. He received the Bergmann Memorial Award from the US-Israel Bi-National Science Foundation (1993), the IBM Faculty Development Award (1994), the IBM Faculty Partnership Award (1995), the Indian Institute of Technology Alumni Leadership Award (2001), the Gödel Prize (2001), and the Distinguished Alumnus Award from the Indian Institute of Technology Kanpur (2006).

Perhaps the best tribute to Motwani is not to quote from the many heartfelt messages that were received after his death, but rather to quote from the acknowledgement that his student Chandra Chekuri wrote in his Ph.D. thesis in 1998:-

Articles:

1. Google mentor Rajeev Motwani dies in freak accident, The Hindu (7 June 2009).
2. S Khuller and S Guha, Guest editors' foreword, Theory of Computing 8 (2012), 53-54.
3. H L Lee, Stanford tech mentor was drunk when he drowned, San Francisco Chronicle (17 July 2009). 
   http://www.sfgate.com/bayarea/article/Stanford-tech-mentor-was-drunk-when-he-drowned-3292527.php#ixzz2TvQsb2P2
4. Professor Rajeev Motwani, The Telegraph (9 June 2009).
5. P Raghavan, Rajeev Motwani (1962-2009), Theory of Computing 8 (2012), 55-68.
6. Rajeev Motwani, computer scientist at Stanford; adviser, investor in Silicon Valley, dead at 47, Stanford Report (6 June 2009). 
   http://news.stanford.edu/news/2009/june10/rajeev_motwani-061009.html
7. Rajeev Motwani passes away, Thaindian News (6 June 2009).
8. Rajeev Motwani: Interview 2002 by Shivanand Kanavi, India Abroad (7 August 2009). 
   http://reflections-shivanand.blogspot.co.uk/2009/08/rajeev-motwani-interview-2002.html
9. Remembering Rajeev Motwani (1962-2009), Stanford University (6 June 2009). 
   http://www.stanford.edu/~ashishg/cgi-bin/RememberingRajeev/
10. A Ricketts, Rajeev Motwani, Google founders' professor and early investor, dies, New York Times (5 June 2009).
11. A Spector, Remembering Rajeev Motwani, Google Research (8 June 2009). 
    http://googleresearch.blogspot.co.uk/2009/06/remembering-rajeev-motwani.html
12. M Weaver, Google founders' mentor found dead in swimming pool, The Guardian (7 June 2009).