MADALGO Theory Seminar: Zengfeng Huang, MADALGO

2014.12.09 | Katrine Østerlund Rasmussen

Date Wed 10 Dec
Time 14:15 15:00
Location Building 5335, Nygaard 395


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



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.