Magnus M. Halldorsson, Reykjavik University, Iceland

Title: Algorithmicist's Agenda for Wireless Networking

Abstract:
Software is bound to play an ever-increasing role in wireless devices, whether in response to demands for smarter use of limited frequency spectrum or for reasons of scalability. This calls for models of wireless communication that are algorithmically usable, especially with respect to the essential aspect of interference.

There have been two main approaches to wireless algorithmics. One camp, originating in computer science theory, demands mathematical rigor with worst-case guarantees, but traditionally using models that abstract away many of the essential characteristics of wireless networks. The other camp, with traditions in engineering, demands realistic models, of varying degree of complexity, but typically focusing on simulations or nicely-distributed instances.

For algorithmicists, the agenda would be to combine the best of both worlds: rigorous results and general properties, using realistic models. Recently, there has been significant progress in understanding the algorithmic properties of the geometric SINR model of wireless interference. We will survey recent results, focusing on unifying themes. We will then explore possible extensions and variations and suggest some future directions.