Exponential Separations in Local Differential Privacy
  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$.
