#### Alladi Ramakrishnan Hall

#### Graph Partitioning for Low Threshold-Rank and Semi-Random Instances

#### Rakesh Venkat

##### Hebrew University, Israel

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

Done