*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching.
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 probability 2/3 is Omega(k R_{1/k}(f)). Since R_{1/k}(f) may be as large as Omega(R_{1/3}(f) log k), we asymptotically beat the 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! In order to achieve this, our direct sum involves a novel measure of information cost which allows a protocol to abort with constant probability, and otherwise must be correct with very high probability. Moreover, for the functions considered, we show strong lower bounds on the communication cost of protocols with these relaxed guarantees; indeed, our lower bounds match those for protocols that are not allowed to abort.
In the distributed and streaming models, where one wants to be correct not only on a single query, but simultaneously on a sequence of n queries, we obtain optimal lower bounds on the communication or space complexity. Lower bounds obtained from our direct sum result show that a number of techniques in the sketching literature are optimal, including the following:
- (JL transform) Lower bound of Omega((1/eps^2) log(n/delta)) on the dimension of (oblivious) Johnson-Lindenstrauss transforms.
- (l_p-estimation) Lower bound for the size of encodings of n vectors in [-M, M]^d that allow l_1 or l_2-estimation of Omega((n/eps^2) log (n/delta) (log d + log M)).
- (Matrix sketching) Lower bound of Omega((1/eps^2) log n/delta) on the dimension of a matrix sketch S satisfying the entrywise guarantee |(ASS^TB)_{i,j} - (AB)_{i,j}| <= eps |A_i|_2 |B^j|_2.
- (Database joins) Lower bound of Omega((n/eps^2) log(n/delta) log M) for sketching frequency vectors of n tables in a database, each with M records, in order to allow join size estimation.
Joint work with David P. Woodruff and Grigory Yaroslavtsev.
