Abstract:

We show a tight lower bound of Omega(N log log N) on the number
of transmissions required to compute the parity of N bits (with
constant error) in a network of N randomly placed sensors,
communicating using local transmissions, and operating with power near
the connectivity threshold. This result settles a question left open
by Ying, Srikant and Dullerud (WiOpt 06), who showed how the sum of
all N bits can be computed using O(N log log N) transmissions.

Our approach is the following.  Using the results of Goyal, Kindler
and Saks (FOCS 05) we show that computations of boolean functions on
noisy wireless networks could be reduced to certain types of
randomized decision trees.  We then show that computations on such
decision trees can be simulated using noiseless algorithms that work
by sampling their inputs, leaving substantial portions of their input
unread.  Our lower bounds will follow immediately from this. As an
illustration of our approach we will show how all the results of Evans
and Pippenger (SIAM J. Computing, 1999) for noisy decision trees, some
of which were derived using Fourier analysis, follow immediately if we
consider the sampling-based algorithms that naturally arise from these
decision trees.

(This is joint work with C. Dutta, Y. Kanoria and D. Manjunath.)