Type of Talk: UTCS Colloquium/ ACT Seminar

Speaker/Aff

illiation: Anup Rao/University of Washington and Princeton University

 Date/Time: Friday, October 16, 2009 11:00 a.m.

 Locat

ion: ACES 2.402

Host: David Zuckerman

Talk Title:  &quot

;Direct Sums in Randomized Communication Complexity"

Talk Abstr

act: 

Is computing multiple copies of a function harder than co

mputing a
single copy? In this work, we give the first non-trivial an

swer to
this question for the model of randomized communication comple

xity.

Ignoring log factors, we prove that:

1. Comput

ing n copies of a function requires  sqrt{n} times the communication.

2. For average case complexity, given any distribution mu on i

nputs,
computing n copies of the function on n independent inputs sam

pled
according to mu requires at least  sqrt{n}  times the
communication
for computing one copy.

3. If mu is a produc

t distribution, computing n copies on n
independent inputs sampled ac

cording to mu requires n times the
communication.

We also s

tudy the complexity of computing the parity of n evaluations
of f, an

d obtain results analogous to those above.

Our results are obtai

ned by designing compression schemes for
communication protocols that

can be used to compress the communication
in a protocol that does not

transmit a lot of information about its
inputs.

This is joi

nt work with Boaz Barak, Mark Braverman and Xi Chen.