Aarhus University Seal / Aarhus Universitets segl

MADALGO Seminar

MADALGO Theory Seminar: Zengfeng Huang, MADALGO

Info about event

Time

Wednesday 10 December 2014,  at 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.