[Colloquium] Nisheeth Vishnoi, IBM India Research Lab- TTI-C Talk

[Julia MacGlashan]

When:             Tuesday, April 29 @ 10:00am

 

Where:            TTI-C Conference Room

 

Who:                Dr. Nisheeth K. Vishnoi, IBM India Research Lab

 

Topic:              Cuts, Embeddings, Flows and Unique Games

 

A fundamental problem in computing is to cut a graph into two "roughly"
equal parts so as to minimize the number of edges crossing the partition.
Interest in this problem derives both from its numerous practical
applications such as image segmentation, VLSI layout, parallel computing and
clustering, and from its theoretical connections to a diverse set of
powerful technical areas such as spectral methods, linear/semi-definite
programming (SDP), measure concentration, metric embeddings, fourier
analysis, probabilistically checkable proofs and the multiplicative weight
update method. In this talk I will address theoretical and applied aspects
concerning graph partitioning.

>From an applied point of view, the main challenge is to design good, yet
scalable algorithms for this problem. The reason being that, in practice,
typical inputs to this problem consist of very large graphs, and hence, it
is imperative to find algorithms that not only run very fast but provide a
guarantee about the quality of the cut they produce. The first major step
towards this was taken by Khandekar, Rao and Vazirani. They reduced the
graph partitioning problem to the computation of a ``small'' number of
max-flows and yet achieved an approximation factor of O(log ^2 n).
In the first half of this talk, I will outline a combinatorial algorithm for
graph partitioning which achieves an O(log n) approximation factor and runs
in essentially max-flow time.  

>From a theoretical standpoint the main question is to determine
approximability of this problem. For the upper bound, a result of Arora, Rao
and Vazirani establishes an O(sqrt(logn)) approximation for this problem.
For the lower bound, nothing much is known beyond NP-hardness. In light of
almost no progress in proving hardness of approximation results, it would be
a wishful conjecture to make  that there is a constant factor approximation
algorithm for graph partitioning. Indeed, an even stronger conjecture was
made by the experts suggesting that, in fact, the ARV algorithm itself is a
constant factor approximation algorithm. This conjecture also had, as
``close cousins'',  certain well-studied and long standing conjectures in
the theory of metric embeddings. In the second half of this talk, I will
give a bird's eye view of the disproof of these conjectures and, time
permitting, their connection to Unique Games.

This talk is based on a series of joint works with Khot [FOCS 05], Devanur,
Khot and Saket [STOC 06], Orecchia, Schulman, (Umesh) Vazirani [STOC 08],
Arora, Khot, Kolla, Steurer, Tulsiani [STOC 08].

 

Contact:          Julia Chuzhoy, TTI-C         cjulia at tti-c.org
834-2490 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080422/9a905b96/attachment.html