MADALGO Seminar
MADALGO Theory Seminar: Zengfeng Huang, MADALGO
Info about event
Time
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.