IC Colloquium : "On the communication complexity of sparse set disjointness and exists-equal problems"
Event details
| Date | 14.10.2013 |
| Hour | 16:15 › 17:30 |
| Speaker | Gabor Tardos |
| Location | |
| Category | Conferences - Seminars |
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.
Probably the two most studied problem in communication complexity are the equality and set disjointness problems. In the former problem Alice and Bob have to decide if their inputs are equal, in the latter they receive subsets of a common ground set and they have to decide if their subsets are disjoint. The complexity of these problems are well established and (in the randomized model) very different.
In this talk I concentrate on variants of these problems: 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 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 a 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 intersection of the input sets.
The exist-equal problem is the OR of several independent equality problems. Our lower bound on the constant round protocols for exists-equal show that
solving the OR of n instances of the equality problem requires strictly more than n times the cost of 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 Sağlam and will appear in the coming FOCS.
Biography:
Gábor Tardos is a Hungarian mathematician, currently a professor and Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science with beautiful results on fingerprint codes, constructive lovasz local lemma, communication complexity, and online algorithms. He received the European Mathematical Society prize for young researchers at the European Congress of Mathematics in 1992 and the Erdős Prize from the Hungarian Academy of Sciences in 2000. He received a Lendület Grant from the Hungarian Academy of Sciences (2009) specifically devised to keep outstanding researchers in Hungary.
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.
Probably the two most studied problem in communication complexity are the equality and set disjointness problems. In the former problem Alice and Bob have to decide if their inputs are equal, in the latter they receive subsets of a common ground set and they have to decide if their subsets are disjoint. The complexity of these problems are well established and (in the randomized model) very different.
In this talk I concentrate on variants of these problems: 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 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 a 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 intersection of the input sets.
The exist-equal problem is the OR of several independent equality problems. Our lower bound on the constant round protocols for exists-equal show that
solving the OR of n instances of the equality problem requires strictly more than n times the cost of 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 Sağlam and will appear in the coming FOCS.
Biography:
Gábor Tardos is a Hungarian mathematician, currently a professor and Canada Research Chair at Simon Fraser University. He works mainly in combinatorics and computer science with beautiful results on fingerprint codes, constructive lovasz local lemma, communication complexity, and online algorithms. He received the European Mathematical Society prize for young researchers at the European Congress of Mathematics in 1992 and the Erdős Prize from the Hungarian Academy of Sciences in 2000. He received a Lendület Grant from the Hungarian Academy of Sciences (2009) specifically devised to keep outstanding researchers in Hungary.
Links
Practical information
- General public
- Free
- This event is internal
Contact
- Host : Ola Svensson