SEMINAR NOTICE

A Tale of Two Ruling Sets

Kishore Kothapalli, Associate Professor, IIIT-H

DATE & TIME : 20 September 2013, 4PM VENUE: SEMINAR ROOM, SCIS

Abstract

Computing an maximal independent set (MIS), also known as a 1-ruling set, is one of the fundamental problems in distributed computing. The best known algorithm to date is still that of Luby from 1985 that runs in O(log n) randomized rounds, where n is the number of nodes in the graph. Only recently, some progress has been made by the work of Barenboim et al. whose algorithm has a smaller run time of O(log Delta . \sqrt{log n) where Delta is the maximum degree of the graph. The above is sub-logarithmic whenever Delta is within 2^{\sqrt{\log n}}.

In this talk, we will first describe a framework called Graph Sparsification that can be used to analyze the algorithm of Barenboim et al. We then proceed to ask whether a relaxed notion of 1-ruling set can lead to faster algorithms. In this context, we describe some recent work that indicates that 2-ruling sets can be computed in strictly sub-logarithmic number of rounds in all cases. The talk concludes by identifying some open problems of rich interest in this area.

BIO

Kishore Kothapalli is presently an Associate professor at the Intenrational Institute of Information Technology, Hyderabad. Prior to that, he obtained his doctoral degree in Computer Science from the Johns Hopkins University with a thesis on efficient algorithms for routing and topology control in dynamic networks. His present research is focused on parallel computing using multi- and many-core architectures, and distributed algorithms for graph problems.