Zero-Error Distributed Function Compression

In this paper, we put forward the model of zero-error distributed function compression system of two binary memoryless sources X and Y as depicted in Fig. 1. In the model, there are two encoders En1 and En2 and one decoder De, connected by two channels with capacity constraints C
1
and C
2
, respectively. The encoder En1 can observe X or (X, Y), and the encoder En2 can observe Y or (X, Y). Here, we use two switches s
1
and s
2
open or closed (taking values 0 or 1) to represent whether En1 can observe Y and En2 can observe X, respectively. The decoder De is required to compress the binary arithmetic sum f(X, Y) = X + Y with zero error by using the system multiple times. We use (s
1
s
2
; C
1
, C
2
; f) to denote the model. The compression capacity is defined as the maximum average number of times that the function f can be compressed with zero error for one use of the system, which measures the efficiency for using the system. In the paper, the compression capacities for all the four models are fully characterized. Amongst them, the characterization of the compression capacity for (01; C
1
, C
2
; f) is very difficult. Toward this end, we develop a novel graph coloring approach in the converse part and the proof is highly nontrivial. Furthermore, we apply the compression capacity for (01; C
1
, C
2
; f) to the open problem in network function computation that whether the best known upper bound by Guang et al. on computing capacity is in general tight. This upper bound is always tight for all previously considered network function computation problems whose computing capacities are known. By considering equivalent network function computation models of (01; C
1
, C
2
; f), we give the answer that in general the upper bound of Guang et al. is not tight.