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