Join us for our Virtual Brown Bag Research Series featuring Rotem Oshman from the University of Toronto.

Abstract:
Today\u2019s wireless networks tend to be centralized: they are organized around a fixed central backbone such as a network of cellular towers or wireless access points. However, as mobile computing devices continue to shrink in size and in cost, we are reaching the point where large-scale ad-hoc wireless networks, composed of swarms of cheap devices or sensors, are becoming feasible. My research studies the theoretical computation power of such networks, and asks what tasks are they capable of carrying out, how long does solving particular tasks take, and what is the effect of the unpredictable network topology on the network\u2019s computation power.

I will describe one particular set of results, focusing on the hardness of aggregating data in wireless networks which suffer from asymmetric communication. I will show that asymmetry can be a major concern: simple tasks such as computing the size of the network, which require only O(D) rounds in symmetric networks of diameter D, now require \\tilde{Omega}(n) rounds in asymmetric networks, even when their diameter is 2; even "easier" tasks, such as computing the minimum input, require \\tilde{Omega}(\\sqrt{n}) rounds. These and related lower bounds are shown by reduction from well-known problems in communication complexity, including Set Disjointness and Gap Hamming Distance. I will also describe a new communication complexity problem, called Task Allocation, give a lower bound on its 2-player communication complexity, and show how it can be applied to obtain an \\tilde{Omega}(n)-round lower bound on finding rooted spanning trees in networks of diameter 2.