Optimal ordering of transmissions for computing Boolean threshold functions
Conference Paper

 Overview

 Identity

 Additional Document Info

 View All

Overview
abstract

We address a sequential decision problem that arises in the computation of symmetric Boolean functions of distributed data. We consider a collocated network, where each node's transmissions can be heard by every other node. Each node has a Boolean measurement and we wish to compute a given Boolean function of these measurements. We suppose that the measurements are independent and Bernoulli distributed. Thus, the problem of optimal computation becomes the problem of optimally ordering nodes' transmissions so as to minimize the total expected number of bits. We solve the ordering problem for the class of Boolean threshold functions. The optimal ordering is dynamic, i.e., it could potentially depend on the values of previously transmitted bits. Further, it depends only on the ordering of the marginal probabilites, but not on their exact values. This provides an elegant structure for the optimal strategy. For the case where each node has a block of measurements, the problem is significantly harder, and we conjecture the optimal strategy. © 2010 IEEE.
name of conference

2010 IEEE International Symposium on Information Theory  ISIT
published proceedings

2010 IEEE International Symposium on Information Theory
author list (cited authors)

Kowshik, H., & Kumar, P. R
citation count
complete list of authors

Kowshik, HemantKumar, PR
publication date
publisher
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 13
Additional Document Info