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).