A Simple Proof of a New Set Disjointness with Applications to Data Streams

Akshay Kamath, Eric Price, David P. Woodruff

The multiplayer promise set disjointness is one of the most widely used problems from communication complexity in applications. In this problem there are $k$ players with subsets $…