UC San Diego

The ever-growing Internet, among other things, provides abundant evidence that we are living in a world of interaction. It is thus of great importance to understand the benefits of interaction in our lives. In this thesis, we investigate the role of interaction in information theory and statistics via three concrete problems: distributed inference, point-to-point channel communication, and communication over networks. First, we consider a classical hypothesis testing problem in a distributed setting, where communication constraints are present. More specifically, two distributed agents, having only partial access to some random data set, are required to perform a hypothesis test regarding the joint data distribution by communicating their observations with each other. The goal is to characterize the optimal tradeoff between the testing performance and the communication budget. We formulate an interactive version of this problem, where the two agents are allowed to communicate in multiple rounds before making a decision. Interestingly, the testing performance can be strictly improved given the same communication budget. Moreover, we study a sequential version of the interactive hypothesis problem which further improves the testing performance. Second, we investigate the role of interaction in the reliability of communication by studying the optimal coding over the Gaussian channel with noisy Gaussian feedback. While it is well known that the reliability of communication can be strictly improved through noiseless feedback, the theoretical understanding of the benefits of noisy feedback is yet far from being complete. We propose two coding schemes that enable strict improvement of the reliability of communication when the noise power in feedback channel is smaller than a certain threshold. Finally, we study the impact of interaction on relay networks. In particular, we focus on a network communication problem, in which one nodes wishes to broadcast a common message to all the other nodes in the network. Typically, relaying schemes are non-interactive, which can be improved by two-round interaction schemes. We investigate this problem beyond the two-round case and demonstrate via a simple example that infinite rounds of interaction can further improve upon finite rounds interactive schemes