In 1998, when Sergey Brin and Larry Page, two computer scientists and PhD students in Stanford, were working on creating what would be one of the biggest companies in the world, an Indian professor helped mentor them. He worked alongside them and co-authored a research paper on the “page rank” algorithm, a criteria still relevant in Google’s search engine. 

Computer Science Professor Rajeev Motwani was not only known for mentoring the Silicon Valley entrepreneurs and backing Google and PayPal during their early days, but was also known for his research work across fields such as computing, robotics and medicine. Rajeev Motwani who tragically died at the young age of 47, was recently commemorated on his birth anniversary on March 24. 

Rajeev Motwani has worked on a number of research papers from late 1990s to early 2000s, wherein his research work laid out foundations for algorithms that were used in future applications. Motwani, a theoretical computer scientist, researched and published works on different areas of computing and algorithms, and even medicine. He has 110,860 citations and 231 publications to his name.

Google Days

Rajeev Motwani, a mentor and guide, has closely worked with Google co-founders Page and Brin. The three of them have worked on multiple papers, the most notable one titled, ‘The PageRank Citation Ranking: Bringing Order to the Web’ in 1998. Along with Terry Winograd, who was another professor at Stanford, they developed the PageRank algorithm that is a method used by Google to rank web pages in its search engine results. PageRank is determined by the number and quality of web pages that link to a site. A concept that was developed during the early stages of Backrub, which later became ‘Google’, is still relevant for the search engine. 

In 1997 and 1998, Motwani co-authored two other papers with Brin, titled, ‘Dynamic itemset counting and implication rules for market basket data’ and ‘Beyond market baskets: Generalizing association rules to correlations’, respectively. Both the papers talk about association rule mining, a concept used for analysing large datasets to find patterns. It is widely used across fields where data is analysed for retail market, healthcare, web mining, and more. 

Sergey Brin reminisced about Motwani after the latter’s untimely demise in 2009. He considered him a “brilliant computer scientist” and a “teacher and good friend”. “His legacy and personality live on in the students, projects, and companies he has touched,” said Brin.   

Motwani’s Priceless Contributions 

One of Motwani’s recognised works is Probabilistically Checkable Proofs (PCP) Theorem. In collaboration with Sanjeev Arora, Carsten Lund, Madhu Sudan and Mario Szegedy, the proposed paper on PCP Theorem has wide applications in theoretical computer science. The authors of this paper were awarded with the Gödel Prize in 2001. The award is considered the most prestigious award given in theoretical computer science. The award is given by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT) . 

The PCP theorem is a mathematical result that states that any problem that can be solved using a computer programme that tries many different solutions—a non-deterministic algorithm—can also be checked using a random sample of the solution rather than checking the whole thing. 

The PCP theorem has had a significant impact on many areas of computer science and related fields and continues to be an active area of research with practical applications. At present, the PCP theorem provides a foundation for secure computation of functions on private data which is useful for applications, such as online transactions and data sharing. In software development, the PCP theorem enables automated checking of programme correctness and, in communication systems, the PCP theorem aids in designing reliable methods for transmitting data over noisy channels. 

Algorithmic Combinatorics and Graph Theory

‘Constructive results from graph minors: Linkless embeddings’ is Motwani’s paper, co-authored with Arvind Raghunathan and Huzur Saran, was published in the Journal of the Association for Computing Machinery (ACM) in 1995. It focussed on constructive results related to “graph minor theorem”. The paper is cited in the field of graph theory, particularly in the study of linkless embeddings and graph minors. 

The paper has been used in various applications and some of the practical examples where this paper is used are in circuit layout designs, network visualisation, network routing, and algorithmic designs in computer vision, computational geometry, and computer graphics. 

Robotics and Medicine

Dating back to 1997, Rajeev Motwani’s interests in geometric computation drove him to contribute towards robotics. Motwani, along with his researchers, released a paper on the Robot Localization Problem in two dimensions. The paper proposed data structures for processing robot localization queries by using a probabilistic approach based on the Monte Carlo method. Future applications of research on robot localization queries are varied. It is used in autonomous vehicles where precise localization is required for accurate navigation as well as in other fields such as augmented reality, robot utilisation industries, and more. 

Motwani, along with a team of researchers, published a paper titled, ‘RAPID: Randomized Pharmacophore Identification for Drug Design’, in the Journal of Medicinal Chemistry in 2002. RAPID is a method for identifying essential structural and chemical features—called pharmacophores—of a molecule that is responsible for its biological activity. This method has the ability to handle large datasets and generate pharmacophores specific to a particular target or class of compounds. The RAPID method is adopted in the field of drug discovery and is used by pharmaceutical companies.  

Mentor and Guide

Motwani was also an active member in student communities. In Stanford, he assisted entrepreneurial student groups, such as BASES and Stanford Student Enterprises. Being an active member in the venture industry, he offered strategic guidance to teams, investors and entrepreneurs. As an advisor to Deutsche Bank, he was one of the first investors in PayPal. 

In 2000, Rajeev and his wife Asha Jadeja Motwani started a venture fund called Dot Edu Ventures that invested in early-stage technology businesses. He was also a special advisor to Sequoia Capital. Rajeev also served as a mentor and board member for IIT Kanpur’s research programme with the Department of Computer Science and Engineering. 

Early Life

Rajeev Motwani graduated from IIT Kanpur in 1983 as one of the first batches of Computer Science students. In 1983, Rajeev joined University of California, Berkeley, to pursue his PhD. He was advised by Professor Richard Karp, computer scientist and computational theorist who won the prestigious Turing award in 1985. In 1988, towards the end of his PhD, at Don Knuth’s request, he joined as a faculty in Stanford. 

Motwani’s famous courses at Stanford include, ‘Automata and Complexity Theory’—a field of computer science that studies abstract machines used for solving computational problems—‘Randomized Algorithms’ and ‘Advanced Data Structures and Algorithms’. Rajeev Motwani also went on to become the Director of Graduate Studies in the Computer Science Department at Stanford.