[A&C Seminar] Beating the Direct Sum Theorem in Communication Complexity
Speaker: Grigory Yaroslavtsev, Penn State
Date: Wednesday, December 12 2012
Time: 4:00PM to 5:00PM
Location: 32-G575
Contact: Eric Price, ecprice@mit.edu
Relevant URL: http://www.mit.edu/~ecprice/algcompsem/
(Note unusual time)
A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1/3 is at least k * R_{1/3}(f), where R_{1/3}(f) is the communication required to solve a single copy of f with error probability 1/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with error probability 1/3 is (k R_{1/k}(f)). Since R_{1/k}(f) may be as large as R_{1/3}(f) * log k, we asymptotically beat the standard direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1 – O(1/k) and taking a union bound is optimal.
Our results imply optimal communication/space lower bounds for several sketching problems in a setting when the algorithm should be correct on a sequence of k queries.
See other events happening in December 2012
