[Colloq] Colloq. Talk by Pradipta Mitra: "Wireless Connectivity from Scratch

[Jessica Biron]

The College of Computer and Information Science presents: 

Title: Wireless Connectivity from Scratch 
Speaker: Pradipta Mitra 
Date: Friday, October 19th, 11:30-12:30 
Location: 366 WVH 

Abstract: 
Starting from basic physical properties of a wireless channel, we consider the problem of constructing a communication infrastructure from scratch, for a collection of identical wireless nodes. This means a) finding a set of links that form a strongly connected spanning graph on a set of $n$ points in the plane, and b) scheduling it efficiently in the SINR model of interference. 

We prove that any set of nodes can be connected in O(\log n) time slots, improving upon a long-standing previous bound of O(\log^2 n). 

We achieve this bound using both centralized and distributed algorithms. The distributed algorithm deploys a two step mechanism: first, a very simple algorithm is used to construct an initial connected tree, this tree is then used a distributed platform to improve itself to come up with a solution matching the centralized bound. 

Talk is based on: 
Wireless Connectivity and Capacity , Magnus M. Halldorsson and Pradipta Mitra , SODA '12 
Distributed Connectivity of Wireless Networks , Magnus M. Halldorsson and Pradipta Mitra , PODC '12 

Bio: 
Pradipta Mitra is a Postdoctoral Researcher at Reykjavik University, where he studies wireless network algorithms. Pradipta completed his PhD in Computer Science from Yale in 2008. He wrote his thesis on clustering algorithms for Random Graphs. Between Yale and Reykjavik, Pradipta worked for Google for a year and half.