Towards a Reverse Newman’s Theorem in Interactive Information Complexity

Algorithmica. 2016. Vol. 76. No. 3. P. 749–781.

Brody J., Buhrman H., Koucký M., Loff B., Speelman F., Vereshchagin N.

 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.

Keywords: compression, communication complexity, Information complexity, information theory, Slepian–Wolf

Publication based on the results of: Теоретическая информатика (2016)