Type of Talk: UTCS Colloquium/ACT Seminar

Speaker/Affiliation: Amit Chakrabarti/Dartmouth

Date/Time: Friday
February 29 2008 11:00 a.m.

Location: ACES 3.408

Host: A

nna Gal

Talk Title: Robust Communication Complexity and Application

s

Talk Abstract:
Communication complexity typically uses the foll

owing setup: Alice
gets *these* specific bits of the input and Bob gets

*those* bits. Do
the lower bounds we know crucially depend on this preci

se
allocation? Or can we prove *robust* lower bounds that hold w.h.p.
for random allocations?

We study the communication complexity of ev

aluating functions
when the input data is randomly allocated (according
to some
known distribution) amongst two or more players possibly with

information overlap. This model naturally extends previously
studi

ed variable partition models such as the best-case and
worst-case partit

ion models. We call a communication lower
bound robust if it holds in

this new model.

A key application is to the heavily studied data str

eam model.
Our communication results imply space lower bounds in the data stream model with the order of the items in the stream
being cho

ng problems.