Theory of Computing ------------------- Title : Special Issue in Honor of Rajeev Motwani (1962-2009): Guest Editors' Foreword Authors : Samir Khuller and Sudipto Guha Volume : 8 Number : 2 Pages : 53-54 URL : https://theoryofcomputing.org/articles/v008a002 Abstract -------- 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 \emph{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, and 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 \emph{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 and Oded Regev for their constant support and careful attention to detail, and to Alex Russell, Ishay Haviv, Ryan Julian, and Yanina Zholudz for their technical assistance. March 24, 2012 Samir Khuller and Sudipto Guha, Guest Editors List of accepted papers "Rajeev Motwani (1962-2009)," by Prabhakar Raghavan, with contributions from Sanjeev Arora, Gautam Bhargava, Piotr Indyk, Asha Jadeja, Sanjeev Motwani, and G. D. Ramkumar. "Regularity Lemmas and Combinatorial Algorithms," by Nikhil Bansal and Ryan Williams. "Online Scheduling to Minimize Maximum Response Time and Maximum Delay Factor," by Chandra Chekuri, Sungjin Im, and Benjamin Moseley. "Improved Bounds for Speed Scaling in Devices Obeying the Cube Root Rule," by Nikhil Bansal, Ho-Leung Chan, Dimitriy Katz, and Kirk Pruhs. "Revenue Submodularity} by Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. "An $O(k^3 \log n)$-Approximation Algorithm for Vertex Connectivity Survivable Network Design," by Julia Chuzhoy and Sanjeev Khanna. "Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality," by Shariel Har-Peled, Piotr Indyk, and Rajeev Motwani. "One Tree Suffices: A Simultaneous $O(1)$-Approximation for Single-Sink Buy-at-Bulk," by Ashish Goel and Ian Post. "Budget-Constrained Auctions with Heterogeneous Items," by Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, and Kamesh Munagala. "Online Graph Edge Coloring in the Random Order Arrival Model," by Bahman Bahmani, Aranyak Mehta, and Rajeev Motwani.