%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% toc-template.tex  2010-09-22
\documentclass{tocforeword}
\newcommand{\eat}[1]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% the following to be completed by the editors
\tocdetails{%
volume=8, number=767, year=2012, firstpage=401,
specissue={\motwani},
%% received={August 3, 2010},
%% revised={Month 33, 2010},
published={March 24, 2012},
doi={10.4086/toc.2010.v008a767}
 }
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%% Running title goes here (same as title, unless very long)
\runningtitle{Foreword to Motwani Special Issue}
%%% Title again, but this time in *plain text*.   %%LB: Running title again??
\tocpdftitle{Foreword to Motwani Special Issue}

\runningauthor{Samir Khuller and Sudipto Guha}
\copyrightauthor{Samir Khuller and Sudipto Guha}
%%% Fill in author names in *plain text* using the 
%%%     format "A", "A, B", "A, B, C", etc.
%%% e.g., Alexander Russell, John Milestone, Kalman Szolossy
\tocpdfauthor{Samir Khuller, Sudipto Guha}
%%%%%%%%%%%%%%%%%
%%Macros, Includes%%

\begin{document}

\begin{frontmatter}
%%% Title goes here
\title{Guest Editors' Foreword}

%\title{
%  \textsc{Foreword}\\
%  \Large{Special Issue in Honor of Rajeev Motwani (1962--2009)}
%}

%%% !!!!
%%% List all authors. List grant acknowledgements in \thanks.
%%% In brackets include a short tag for each author.
\author[khuller]{Samir Khuller}
\author[guha]{Sudipto Guha}

%\author{Samir Khuller and Sudipto Guha, Guest Editors}

%%%  Your abstract goes here

\tocacm{K.2/People, F.2.2}
\tocams{01A70, 68-00}
\tockeywords{foreword, special issue, Motwani special issue}
\end{frontmatter}

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 special issue of \emph{Theory of Computing,}
launched on the 50th anniversary of his birth (March 24, 1962),  %%LB ???
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, 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 normal stringent standards of
\emph{Theory of Computing}.
The papers will be released individually over the next several months.
The list of accepted papers is appended below.

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 in many matters involving this special
issue.

\newpage
%% \eat{

\noindent
{\Large List of currently accepted papers}

\smallskip\noindent
This list will be updated as we complete the issue.


\begin{itemize}
\item \emph{Rajeev Motwani (1962-2009),} by Prabhakar Raghavan, with
contributions from Sanjeev Arora, Gautam Bhargava, Piotr Indyk, Asha Jadeja, 
and Sanjeev Motwani.

\item  \emph{Regularity Lemmas and Combinatorial Algorithms,}
 by Nikhil Bansal and Ryan Williams.

\item \emph{Online Scheduling to Minimize Maximum Response Time and 
Maximum Delay Factor,} by Chandra Chekuri, Sungjin Im, and Benjamin Moseley. 

\item \emph{Improved Bounds for Speed Scaling in Devices Obeying the 
Cube Root Rule,} 
by Nikhil Bansal, Ho-Leung Chan, Dimitriy Katz, and Kirk Pruhs.

\item \emph{Revenue Submodularity} by Shaddin Dughmi, Tim Roughgarden, and 
Mukund Sundararajan.

\item \emph{An $O(k^3 \log n)$-Approximation Algorithm for Vertex Connectivity
Survivable Network Design,} by Julia Chuzhoy and Sanjeev Khanna.

%\item \emph{Budget Constrained Auctions with Heterogeneous Items,} by
%Bhattacharya, Ashish Goel, Gollapudi and Munagala.

\item \emph{ Approximate Nearest Neighbor: Towards Removing the Curse of 
Dimensionality,} by Shariel Har-Peled, Piotr Indyk, and Rajeev Motwani.

\item \emph{One Tree Suffices: A Simultaneous $O(1)$-Approximation for 
Single-Sink Buy-at-Bulk,} by Ashish Goel and Ian Post.

\end{itemize}

%%}

\bibliographystyle{tocplain}  
%%% !!!
%%% Change this to match the name of your BIB file
%% \bibliography{cs-econ}

%%\bibliography{v008a767}

\begin{tocauthors}
\begin{tocinfo}[khuller]
Samir Khuller \\
Department of Computer Science, \\
University of Maryland \\
College Park, MD \\
samir\tocat{}cs\tocdot{}umd\tocdot{}edu \\
\url{http://www.cs.umd.edu/~samir/}
\end{tocinfo}
\begin{tocinfo}[guha]
Sudipto Guha \\
Department of Computer and Information Science, \\
University of Pennsylvania \\
Philadelphia, PA \\
sudipto\tocat{}cis\tocdot{}upenn\tocdot{}edu \\
\url{http://www.cis.upenn.edu/~sudipto/}
\end{tocinfo}
\end{tocauthors}

\end{document}


