Abstract:

"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.

Joint work with Marco Molinaro and David Woodruff (SODA'13)