Speaker

Prof.Gabor Tardos, Rényi Mathematical Institute of the Hungarian Academy of Sciences  

　　Title

On the Communication Complexity of Sparse Set Disjointness  

　　Time

　　Venue

N702

　　Abstract

 In communication complexity one concentrates on a single aspect of computation and asks how long messages need to be exchanged and in how many rounds between two parties (traditionally Alice and Bob) if they want to evaluate a function that depends on both of their inputs. This lead to a very clean model and allowed us to better understand certain aspects of complexity, including proving meaningful lower bounds for certain problems that are famously lacking for more standard computational models. Among the many applications are those for streaming algorithms, a widely studied topic in complexity.
One of the most studied and best understood problems in communication complexity is the set disjointness problems. Alice and Bob receive subsets of a common ground set and they have to decide whether their subsets are disjoint.
In this talk I concentrate on a variants of this problem. In the sparse set disjointness problem Alice and Bob receive SMALL subsets of a large ground set and they still have to figure out if their sets are disjoint. For this problem, we give a probabilistic protocol that communicates a total of O(k log^{(r)} k) bits over r rounds and errs with very small probability. Here k is the size of the input sets and log^{(r)} is the r-times-iterated log function. This is optimal for any value of r. We can take r = log^*k to obtain an O(k) total communication log^*k-round protocol with exponentially small error probability, improving on the O(k) bits O(log k) round constant error probability protocol of Hastad and Wigderson from 1997. A small variation of our protocol even finds the entire intersection of the input sets, rather than only decides whether it is empty or not.
The lower bound showing the tightness of our results is based on a variant of the equality function and shows counterintuitively that solving the OR of n instances of the equality problem in bounded number of rounds requires strictly more than n times the cost of solving a single instance. To our knowledge this is the first example of such a super-linear increase in complexity.
The results are joint with Mert Saglam and appeared in FOCS 2013.    

　　Affiliation

Professor Gabor Tardos received his Ph.D. degree in Mathematics from E?tv?s University, in 1988 and has been a research fellow at the Rényi Mathematical Institute of the Hungarian Academy of Sciences, since 1990. He was Canada Research Chair of computational and discrete geometry at Simon Fraser University, 2005 -- 2013. Professor Tardos was awarded the Prize of the first European Congress of Mathematics in 1992, and the Erd?s Prize from the Hungarian Academy of Sciences in 2000. He received Corvin Chain Fellowship in 2002 and a Lendület Grant from the Hungarian Academy of Sciences in 2009. His research interests include combinatorics, discrete and computational geometry, and complexity theory.