Optimal Computation of Symmetric Boolean Functions in Tree Networks

Date Added: Apr 2010
Format: PDF

In this paper, the authors address the scenario where nodes with sensor data are connected in a tree network, and every node wants to compute a given symmetric Boolean function of the sensor data. They first consider the problem of computing a function of two nodes with integer measurements. They allow for block computation to enhance data fusion efficiency, and determine the minimum worst-case total number of bits to be exchanged to perform the desired computation. They establish lower bounds using fooling sets, and provide a novel scheme which attains the lower bounds, using information theoretic tools. For a class of functions called sum-threshold functions, this scheme is shown to be optimal.