# Simulating Noisy Channel Interaction

## Author(s): Braverman, Mark; Mao, Jieming

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr19c1d
 Abstract: We show that T rounds of interaction over the binary symmetric channel BSC1/2--ε with feedback can be simulated with O(ε2T) rounds of interaction over a noiseless channel. We also introduce a more general "energy cost" model of interaction over a noisy channel. We show energy cost to be equivalent to external information complexity, which implies that our simulation results are unlikely to carry over to energy complexity. Our main technical innovation is a self-reduction from simulating a noisy channel to simulating a slightly-less-noisy channel, which may have other applications in the area of interactive compression. Publication Date: 2015 Citation: Braverman, Mark, and Jieming Mao. "Simulating noisy channel interaction." In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science (2015): pp. 21-30. doi:10.1145/2688073.2688087 DOI: 10.1145/2688073.2688087 Pages: 21 - 30 Type of Material: Conference Article Journal/Proceeding Title: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science Version: Author's manuscript