Exponential Separations in Local Differential Privacy Through Communication Complexity

Matthew Joseph, Jieming Mao, Aaron Roth

[arXiv]

We prove a general connection between the communication complexity of two-player games and the sample complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from communication complexity. In particular, we 1) use a communication lower bound for the hidden layers problem to prove an exponential sample complexity separation between sequentially and fully interactive locally private protocols, and 2) use a communication lower bound for the pointer chasing problem to prove an exponential sample complexity separation between k round and k+1 round sequentially interactive locally private protocols, for every k