<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br>Sushant Sachdeva will present his preFPO on Tuesday March 12 at 11AM in Room 302 (note room!). <br>The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Nisheeth <br>Vishnoi (MSR India) readers; Beranrd Chazelle and Mark Braverman, nonreaders. Everyone <br>is invited to attend his talk. His abstract follows below.<div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div dir="ltr"><div><br></div><div>==============================================</div><div><div>New Results in Graph Partitioning and Optimal Inapproximability</div>
<div>sans UGC</div><div><br></div><div>This thesis consists of two parts. The first part contains improved</div><div>algorithms for graph partitioning problems, both for well-studied</div><div>classical problems (Balanced Separator) and for more practically</div>
<div>motivated problems (Identifying Communities). The second part contains</div><div>new results towards achieving optimal inapproximability results</div><div>without assuming the Unique Games Conjecture.</div><div><br>
</div>
<div>A. Graph Partitioning</div><div>We give the first near-linear time algorithm for Balanced Separator</div><div>with the best possible guarantee for spectral algorithms. The</div><div>algorithm combines SDP rounding techniques with continuous time random</div>
<div>walks on the graph. We show how to approximate these walks, or</div><div>equivalently, the matrix exponential e^{-tL}, where L is the graph</div><div>Laplacian, in near-linear time, by combining techniques from</div>
<div>approximation theory and numerical linear algebra.</div><div><br></div><div>We give a novel approach to the problem of identifying communities in</div><div>a graph representing a social network. We model the network as being</div>
<div>described by overlapping communities with certain local structure; and</div><div>under these assumptions, we provably and efficiently recover the</div><div>underlying communities.</div><div><br></div><div>B. Optimal Inapproximability without assuming UGC</div>
<div>We study the inapproximability of some classic scheduling problems</div><div>viz. Concurrent Open Shop and the Assembly Line problem, and prove an</div><div>optimal 2-inapproximability for both problems assuming P != NP.</div>
<div>Previously, the best NP-hardness factors known were 6/5 and 1+eps</div><div>respectively. We also study the inapproximability of Hypergraph Vertex</div><div>Cover on k-uniform k-partite hypergraphs, and prove a nearly optimal</div>
<div>NP-hardness of approximating it within k/2-1, where a</div><div>k/2-approximation is known due to Lovász.</div><div><br></div><div>The results in this talk are based on joint works with Sanjeev Arora,</div><div>Rong Ge, Lorenzo Orecchia, Rishi Saket, Grant Schoenebeck, Madhur</div>
<div>Tulsiani, and Nisheeth K. Vishnoi.</div></div><div><br></div></div>
</div><br></div></body></html>