Abstract
I'll discuss various tools for proving lower bounds in the message passing communication model, where there are k players each with an input who speak to each other in a point-to-point communication network, with the goal being to solve a function of their inputs while minimizing total communication. I'll mostly focus on several recent works in which the servers try to estimate the number of distinct elements on the union of their datasets, though I'll also discuss results for graph problems, linear-algebraic problems, and other statistical problems.
This is based on joint works with Yi Li, Xiaoming Sun, Chengu Wang, and Qin Zhang.