Towards a Reverse Newmans Theorem in Interactive Information Complexity Newmanu0027s theorem states that we can take any publiccoin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new directsum theorems through the compression of interactive communication in the boundedround setting. To obtain this application, we prove a new oneshot variant of the SlepianWolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newmanu0027s Theorem can be proven in full generality, then full compression of interactive communication and fullygeneral directsum theorems will result.

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.