Speaker: Chinmoy Dutta
Tata Institute of Fundamental Research, Mumbai
Title: Lower Bounds for Noisy Wireless Networks via Sampling Algorithms
Abstract:
We show a tight lower bound of \Omega(N log log N) on the number of
transmissions required to compute several functions (including the
PARITY function and the MAJORITY function) in a network of N randomly
placed sensors, communicating using local noisy transmissions. This
result considerably simplifies and strengthens an earlier result of
Dutta, Kanoria, Manjunath and Radhakrishnan (SODA 08) that such networks
cannot compute the PARITY function reliably with significantly fewer
than (N log log N) transmissions, thereby showing that the protocol to
compute the SUM with O(N log log N ) transmissions due to Ying, Srikant
and Dullerud (WiOpt 06) is optimal. We also observe that all the lower
bounds shown by Evans and Pippenger (SIAM J. on Computing, 1999) on the
average noisy decision tree complexity for several functions can be
derived using our technique simply and in a unified way.
This is a joint work with Jaikumar Radhakrishnan (TIFR, Mumbai).