Interactive source coding for function computation in networks

Today coding-blocklength, rate, signal-to-noise ratio, frequency, and network-size, are well recognized and studied resources for communication and computation in information theory. A relatively less recognized and understood resource is interaction, that is, the number of rounds of two-way information exchange.;This thesis undertakes a comprehensive mathematical analysis of the benefits of interaction for distributed computation in source networks using the information-theoretic framework of distributed block source coding. The ultimate limits of computation efficiency for two-terminal and certain types of collocated networks are characterized in terms of the statistical dependencies between the information sources and the structure of the desired functions. A blueprint for designing a new family of distributed source codes for general networks is developed where interaction protocols can harness the structure of the functions, the network topology, and the statistical dependencies to maximize the computation-efficiency.;A novel viewpoint is introduced in which the minimum sum-rate is viewed as a functional of the joint source distribution and distortion levels. Certain convex-geometric properties of this functional are established and used to develop a new type of blocklength-free single-letter characterization of the ultimate limit of interactive computation involving potentially an infinite number of infinitesimal-rate messages. The traditional method for single-letter characterization is shown to be inadequate. The new characterization is used to derive closed-form analytic expressions of the infinite-message minimum sum-rates for specific examples and an efficient iterative algorithm for numerically evaluating any finite-message minimum sum-rate for the general case. It is also used to construct the first examples which demonstrate that for lossy source reproduction, two messages can strictly improve the one-message Wyner-Ziv rate-distortion function settling an open question from a 1985 paper.;For computing symmetric functions of binary sources in collocated networks, a new lower bound of the minimum sum-rate is derived and shown to be order-wise tight while the cut-set bound is shown to be order-wise loose. Striking examples are constructed to highlight the benefits of interaction: in a two-terminal network a single backward message can lead to an arbitrarily large gain in the sum-rate and in a star network interaction can change the sum-rate by an order-of-magnitude.