Today, blocklength, rate, SNR, frequency, quantizer resolution, and network size are well-studied and recognized resources for communication in information theory. A relatively less well recognized and less understood resource for communication and computation is interaction. Interaction as a resource becomes particularly valuable in the context of distributed function computation where it may be necessary for nodes to exchange information bidirectionally, perform computations, and harness the structure of the functions, statistical-dependencies, and the network topology to maximize the overall computation-efficiency as opposed to only generating, receiving, and forwarding data.
This talk will focus on a distributed block source coding problem involving potentially an infinite number of messages with infinitesimal-rate for two-terminal interactive function computation.Viewing the sum-rate-distortion function as a functional of the joint source pmf and distortion levels, I will describe a new type of single-letter characterization of the infinite-message limit. I will show how this leads to an iterative algorithm for numerical evaluation and the first example demonstrating that two messages can strictly improve the one-message Wyner-Ziv rate-distortion function resolving a question raised by Kaspi in 1985. In closing, I will briefly mention extensions to star networks where interaction changes the scaling law of the sum-rate in terms of the network size and collocated networks where for computing symmetric functions of binary sources, a new lower bound for the minimum sum-rate is order-wise tight whereas the cutset bound is order-wise loose.
Nan Ma received his Bachelor’s degree and Master’s degree in Electronic Engineering from Tsinghua University in 2002 and 2005, respectively. Since 2005 He is a PhD student in the Department of Electrical and Computer Engineering at Boston University. He is currently working on Network Information Theory problems related to distributed data processing and communication which are motivated by emerging applications such as wireless sensor networks, multicore GPUs, and distributed and cloud computing. In his doctoral dissertation entitled “Interactive Source Coding for Function Computation in Networks”, he comprehensively studied the problem of two-way interactive computation where messages are allowed to be sent back and forth between the terminals. In particular, his research has exposed the great benefits of interaction in network function computation problems. He has also worked on problems in optical communication systems, field reconstruction problems in sensor networks and sequential coding problems motivated by video coding applications. His technical interests include Communications, Information Theory, Signal Processing, Data/Sensor Networks, and Image and Video Processing.
