Strong Lower Bounds for Multi-Party Equality with Applications

We give new lower bounds for multi-party communication problems based on the basic Equality predicate, but incorporating strong promises. These promises make our bounds stronger than what was known before. We also give some applications of these bounds to data stream problems. In particular, we obtain strong space/approximation tradeoffs showing that for deterministic algorithms, even loose estimations of some basic statistics of an input stream require large, even linear, amounts of space.

 

This work is joint with Sagar Kale (Dartmouth).