Title

The Deterministic Communication Complexity of Distributed $\eps$-Approximations

Abstract

Data summarization is an effective approach to dealing with the ``big data'' problem.

While data summarization problems traditionally have been studied is the streaming

model, the focus is starting to shift to distributed models, as distributed/parallel

computation seems to be the only viable way to handle today's massive data sets.  In

this talk, I will talk about $\eps$-approximations, a classical data summary that,

intuitively speaking, preserves approximately the density of the underlying data set

over a certain range space.  We consider the problem of computing

$\eps$-approximations for a data set which is held jointly by $k$ players, and prove an

optimal deterministic communication lower bound for halfplanes.