TY - GEN
T1 - Simulating noisy channel interaction [extended abstract]
AU - Braverman, Mark
AU - Mao, Jieming
PY - 2015/1/11
Y1 - 2015/1/11
N2 - 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.
AB - 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.
KW - Communication complexity
KW - Information complexity
KW - Noisy channel
UR - http://www.scopus.com/inward/record.url?scp=84922147540&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84922147540&partnerID=8YFLogxK
U2 - 10.1145/2688073.2688087
DO - 10.1145/2688073.2688087
M3 - Conference contribution
AN - SCOPUS:84922147540
T3 - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
SP - 21
EP - 30
BT - ITCS 2015 - Proceedings of the 6th Innovations in Theoretical Computer Science
PB - Association for Computing Machinery, Inc
T2 - 6th Conference on Innovations in Theoretical Computer Science, ITCS 2015
Y2 - 11 January 2015 through 13 January 2015
ER -