Collection Nexus Trimester - 2016 - Distributed Computation and Communication Theme
Organisateur(s)
Date(s)
19/05/2024
On the Ultimate Limit of Two-Terminal Interactive Computing
We approach two-terminal interactive computing via distributed source coding in information theory. We characterize the minimum rate (bits per sample) for asymptotically error free computation when there is no limit on the number of messages that can be exchanged. Here, the minimum rate is viewed as a functional of the joint source distribution. The functions to be computed at the two terminals can be different. The functional characterization leads to _exact_ analytic closed-form expressions for the minimum rates for computing any Boolean function of independent inputs at only one terminal and both terminals. It also leads to an alternating “concavification” algorithm for approximating the minimum rate for general functions and distributions. We conclude by discussing connections to amortized distributional communication complexity and some open problems. This is based on joint work with Nan Ma at Boston University.
