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:

https://www.youtube.com/watch?v=DNvK2FvB-bA&list=PL_0phSnA7tyQJDn-5hacAu...