Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

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!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login