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.