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.