Communication complexity of sparse disjointness

PhD Student Seminar
Open to the Public
Zrinyi u. 14
Wednesday, March 5, 2014 - 2:00pm
Add to Calendar
Wednesday, March 5, 2014 - 2:00pm to 3:30pm

Abstract: In the communication complexity model a function is to be
computed by several (in most cases two) parties knowing different
parts of the inputs. The goal is to compute the output with as few and
short messages exchanged between the parties as possible, while
internal calculations of the participants is "for free". The most well
studied "standard" problems in computational complexity are equality
and set disjointness. They behave rather differently in the randomized
model. We consider slight variants of these classical problems:
disjointness of small sets and the several independent equality
problems. We give tight tradeoffs between the number of messages to
compute them and the length of these messages. We improve on the
protocol of Hastad and Wigderson for small set intersection by
reducing the number of rounds needed and the error probability and
giving the exact intersection as output rather than just a yes or no
answer for disjointness. We also show that the complexity of computing
the OR of n equality problems can increase more than n-fold compared
to computing a single one - a rather counterintuitive result.
These results are joint with Mert Saglam of the University of Washington.

You can watch the lecture here: