Theory of Computing

Special Issue in honor of Rajeev Motwani (1962 -- 2009)

Submit by: July 30, 2010

Rajeev Motwani was a pioneer.  In addition to his core contributions to theoretical computer science, he was also one of the ambassadors of Theory to the broader Computer Science community. 


Rajeev's work in TCS focused on randomized algorithms and on approximation algorithms.  He made fundamental theoretical contributions to a number of areas, including motion planning, databases, and scheduling.  He was one of the authors of the celebrated PCP theorem.


Rajeev's interest in problems relevant to practice helped establish new paradigms such as data streaming, nearest neighbor search, data privacy.  He worked in diverse fields such as robotics and computational drug design, and made seminal contributions to web search and data mining.


To honor Rajeev's legacy in the theory of computing, we are announcing a special issue of the journal Theory of Computing.  Submissions should be made by email through the journal's submission process described on the website  Authors should put "ToC submission: Motwani special issue" in the Subject and Cc the submission to


All submissions will undergo a thorough review and will have to meet the stringent standards of Theory of Computing We expect to complete the review of the papers by January 2011 (earlier submissions shall be processed faster).



Sudipto Guha, guest editor,
Samir Khuller, guest editor,
Laszlo Babai, editor, Theory of Computing,