Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

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)

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: 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