Rajeev Motwani's outstanding contributions to theoretical computer science, in diverse topics such as probabilistically checkable proofs, algorithmic combinatorics, streaming algorithms, and similarity search, to name just a few, have had an indelible influence on the field. This issue of Theory of Computing, opened on the 50th anniversary of his birth (March 24, 1962), commemorates Rajeev Motwani's life, scientific work, and legacy.

We thank Prabhakar Raghavan for compiling an article on Rajeev Motwani's life and scientific work, based on contributions from Sanjeev Arora, Gautam Bhargava, Piotr Indyk, Asha Jadeja, Sanjeev Motwani, and G. D. Ramkumar, as well as on his own recollections.

Rajeev Motwani died tragically on June 5, 2009 at the age of 47, and he is sorely missed by his family, friends, colleagues, and fellow researchers. His influence and strong legacy are evidenced by the papers in this issue, which draw upon his work. The papers are in the areas of scheduling, graph algorithms, algorithmic game theory, approximation algorithms, and high-dimensional computational geometry, which is representative of Rajeev Motwani's wide-ranging interests and the breadth of his contributions.

Submissions to this special issue were solicited in 2010. The papers appearing were selected from those submitted, after reviews following the stringent standards of Theory of Computing. The papers will be released individually over the next several months.

We thank the authors of these papers for their contributions, and the anonymous reviewers for their meticulous and timely work. We also thank Laci Babai, Oded Regev, and John Watrous for their constant support and careful attention to detail, and to Alex Russell, Ishay Haviv, Ryan Julian, and Yanina Zholudz for their technical assistance.

The publication of the Special Issue was completed on December 9, 2012.

Motwani Special Issue Table of Contents