Home
Speakers
Schedule
Location and Directions
Hotel Information
Munther Dahleh
Massachusetts Institute of Technology
Title: Information Theoretic Bounds for Distributed Computation
Abstract: In this work, we explore the impact of constraints imposed by a communication network on distributed computation. In this formulation, nodes make partial observations of an underlying source. They communicate, through a noisy channel, in order to compute a given function of all the measurements in the network, to within a desired level of error in terms of the mean square distance between the estimate and the actual function. Such computation in networks arises in various contexts, like wireless and sensor networks, consensus and belief propagation with bit constraints, and estimation of a slowly evolving process. In such contexts, the nodes do not know the distribution of the source, but we assume they have unlimited computation power to run whatever algorithm needed to ensure the mean square error criterion. The question is: how does the communication network impact the time until the performance criterion is guaranteed. We utilize Information Theoretic formulations and tools to obtain code- or algorithm-independent lower bounds that capture fundamental limits imposed by the communication network. Such lower bounds depend on the network topology, the link capacities, and the actual function to be computed. In certain context, such bounds are shown to be tight. Joint work with: Ola Ayaso and Devavrat Shah