 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Wednesday, July 17, 2013, 12:15 pm

Duration: 30 minutes

Location: CAB G11

Speaker: Mert Saglam (University of Washington)

## On the communication complexity of sparse set disjointness and exists-equal problems

In communication complexity, two players, Alice and Bob are given separate inputs x and y, respectively, and they exchange bits according to a protocol in order to compute f(x,y), where f is a function known to both. In a randomized protocol, the players can further base their actions on coin tosses and they have to output f(x,y) with probability ⅔ for each (x,y). In an r-round protocol the players can take at most r turns alternately sending each other a bit string (called a message).

Perhaps the most studied problem is the disjointness function, where the players are given a subset of [m] each, and they are required to decide if their sets intersect. This can be trivially achieved using O(m) bits in 1 round. Classical results show that Ω(m) bits is best possible, even for randomized protocols with arbitrary number of rounds.

In case the sets players receive have at most k < m elements, then there is even a O(k) bits protocol by Håstad and Wigderson. This protocol runs in O(log k) rounds and errs with 1% probability. We improve this protocol to run in log*k rounds and to exponentially small error. In fact, for any r, the protocol runs in r rounds by exchanging a total of O(k log(r) k) bits and errs with very small probability (well below inverse polynomial of k).

Our main contribution is a tightly matching lower bound: we show that an Ω(k log(r) k) bits lower bound holds, for any randomized protocol (even those with ⅓ error probability) and even for an easier and natural problem. The lower bound is obtained via a round elimination argument and at the heart of this argument is a new isoperimetric inequality in the high dimensional grid [t]^n. Our lower bound also exhibits the first known case of super-sum in communication complexity: computing the OR of n instances of equality problem requires strictly more than n times the resources needed for a single instance of the problem when the number of rounds is less than log*n.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks