Aarhus University Seal


MADALGO Theory Seminar: Zengfeng Huang, MADALGO

Info about event


Wednesday 10 December 2014,  at 14:15 - 15:00


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.