<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<style>
<!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
p
{mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman";}
span.EmailStyle18
{mso-style-type:personal;
font-family:Arial;
color:windowtext;}
span.EmailStyle19
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle20
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle21
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle22
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle23
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle24
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle25
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle26
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle27
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle28
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle29
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle30
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle31
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle32
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>When:
Tuesday,
April 29 @ 10:00am<b><span style='font-weight:bold'><o:p></o:p></span></b></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Where:
TTI-C Conference Room<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p style='margin:0in;margin-bottom:.0001pt'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Who:
Dr. Nisheeth K. Vishnoi, IBM India Research Lab<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=3 face=Arial><span
style='font-size:12.0pt;font-family:Arial'>Topic:
Cuts,
Embeddings, Flows and Unique Games<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p><font size=3 face=Arial><span style='font-size:12.0pt;font-family:Arial'>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.<o:p></o:p></span></font></p>
<p style='margin-bottom:12.0pt'><font size=3 face=Arial><span style='font-size:
12.0pt;font-family:Arial'>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).<br>
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. <br>
<br>
>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.<br>
<br>
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].<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Contact:
Julia Chuzhoy,
TTI-C cjulia@tti-c.org
834-2490 <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'> <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
</div>
</body>
</html>