UTCS Colloquium/ACT Seminar: Amit Chakrabarti/Dartmouth Robust Communication Complexity and Applications ACES 3.408 Friday February 29 2008 11:00 a.m.

Contact Name: 
Jenna Whitney
Date: 
Feb 29, 2008 11:00am - 12:00pm

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

sen not adversarially but rather uniformly from the
set of all permutat

ions.

Our results include the first robust lower bounds for (two-an

d
multi-party) set disjointness and gap-Hamming-distance (both
tight

) and for tree pointer jumping. Collectively these yield
lower bound

s for a variety of problems in the random-order
data stream model incl

uding estimating the number of distinct
elements approximating frequenc

y moments median finding
quantile estimation and certain graph streami

ng problems.