MADALGO Theory Seminar: Zengfeng Huang, MADALGO
2014.12.09 |
| Date | Wed 10 Dec |
| Time | 14:15 — 15:00 |
| Location | Building 5335, Nygaard 395 |
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.