Communication complexity of sparse disjointness скачать в хорошем качестве

Communication complexity of sparse disjointness

Speaker: Gábor Tardos (CEU, Renyi Institute) 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.