Invited Talk by Dr. Rakesh Venkat on Graph Partitioning for Low Threshold-Rank and Semi-Random Instances

Title: Graph Partitioning for Low Threshold-Rank and Semi-Random Instances
Speaker : Dr. Rakesh Venkat, Hebrew University of Jerusalem, Israel.
Host Faculty : Dr.Subrahmanyam Kalyanasundaram
Date: 4th July 2018
Time: 11:30am to 12:30am.
Venue: C Block LH-5.

Abstract:

Graph partitioning refers to a class of algorithmic problems that ask for a partition of an input graph $G$ into two or more parts, while optimizing an objective function that measures the quality of the partition. One natural criteria that is of both theoretical and practical significance is that the cuts are ‘sparse’: they split the graph into balanced parts with very few interactions across the parts. Although these problems are usually NP-Hard to approximate (up to large factors) in the general case, input graphs in practice often have some kind of structure that could help one find better sparse cuts more efficiently. This presents us with the natural question of designing algorithms that give better guarantees or are more efficient for such input instances.

In this talk, we will mainly focus on how the Sparsest Cut problem can be solved efficiently on a class of graphs called low threshold-rank graphs. The Sparsest Cut objective measures the sparsity of a cut in terms of edges going across the cut, normalized by the size of the partition. While the best known approximation guarantee for this problem is $O(\sqrt{log n})$ in general, we show that one can do much better on graphs which already have a ‘clustered’ structure, using an efficient and intuitive algorithm. Our algorithm also furnishes a generalization of a geometric theorem of Goemans on embedding finite metric spaces into $\ell_1$.

In the latter part of the talk, we will briefly look at a natural semi-random model of generating ‘clustered’ input graphs where a better objective is to consider the number of boundary vertices on the cut, as opposed to edges across it. We will see an outline of how to exactly recover a sparse vertex-cut in this setting using Semidefinite Programming.

(Based on joint works with Amit Deshpande, Prahladh Harsha, Anand Louis and Yuval Rabani).

Speaker Bio:

Rakesh Venkat is currently a Postdoctoral Fellow at the Hebrew University of Jerusalem, Israel. He received his PhD from TIFR, Mumbai. Prior to that he obtained his B.Tech, M.Tech degrees in Computer Science from IIT-Bombay. His research interests include topics in approximation algorithms, spectral graph theory and complexity theory.

Dates:
Wednesday, July 4, 2018 - 11:30 to 12:30