### ?

## Towards a Reverse Newman’s Theorem in Interactive Information Complexity

Newman's theorem states that we can take any public-coin

communication protocol and convert it into one that uses only

private randomness with only 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 direct sum

theorems through the compression of interactive communication in the

bounded-round setting. Furthermore, we show that if a Reverse

Newman's Theorem can be proven in full generality, then full

compression of interactive communication and fully-general

direct-sum theorems will result.