Exponential Separations in Local Differential Privacy. We prove a general connection between the communication complexity of twoplayer games and the sample complexity of their multiplayer 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 k1 round sequentially interactive locally private protocols, for every k.

Two Party Distribution Testing: Communication and Security We study the problem of discrete distribution testing in the twoparty setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over n, and they need to test whether ab or a,b are epsilonfar for some fixed epsilonu003e0. This is in contrast to the wellstudied oneparty case, where the tester has unrestricted access to samples of both distributions, for which optimal bounds are known for a number of variations. Despite being a natural constraint in applications, the twoparty setting has evaded attention so far.  :96,address two fundamental aspects: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each otheru0027s input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent of epsilonfar from being independent.  :164,contribution is threefold:  :168,Communication: we show how to gain communication efficiency with more samples, beyond the informationtheoretic bound on t. The gain is polynomially better than what one obtains by adapting standard algorithms.  :199,Lower bounds: we prove tightness of our protocols for the closeness testing, and for the independence testing when the number of samples is unbounded. These lower bounds are of independent interest as these are the first 2party communication lower bounds for testing problems.  :243,Security: we define secure distribution testing and argue that it must leak at least some minimal information. We then provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.