To refer to this page use:
|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.|
|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|
|Pages:||21 - 30|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.