[talks] S Sachdeva preFPO

[Melissa M. Lawson]

Sushant Sachdeva will present his preFPO on Tuesday March 12 at 11AM in Room 302 (note room!). 
The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Nisheeth 
Vishnoi (MSR India) readers; Beranrd Chazelle and Mark Braverman, nonreaders. Everyone 
is invited to attend his talk. His abstract follows below. 




============================================== 

New Results in Graph Partitioning and Optimal Inapproximability 
sans UGC 


This thesis consists of two parts. The first part contains improved 
algorithms for graph partitioning problems, both for well-studied 
classical problems (Balanced Separator) and for more practically 
motivated problems (Identifying Communities). The second part contains 
new results towards achieving optimal inapproximability results 
without assuming the Unique Games Conjecture. 


A. Graph Partitioning 
We give the first near-linear time algorithm for Balanced Separator 
with the best possible guarantee for spectral algorithms. The 
algorithm combines SDP rounding techniques with continuous time random 
walks on the graph. We show how to approximate these walks, or 
equivalently, the matrix exponential e^{-tL}, where L is the graph 
Laplacian, in near-linear time, by combining techniques from 
approximation theory and numerical linear algebra. 


We give a novel approach to the problem of identifying communities in 
a graph representing a social network. We model the network as being 
described by overlapping communities with certain local structure; and 
under these assumptions, we provably and efficiently recover the 
underlying communities. 


B. Optimal Inapproximability without assuming UGC 
We study the inapproximability of some classic scheduling problems 
viz. Concurrent Open Shop and the Assembly Line problem, and prove an 
optimal 2-inapproximability for both problems assuming P != NP. 
Previously, the best NP-hardness factors known were 6/5 and 1+eps 
respectively. We also study the inapproximability of Hypergraph Vertex 
Cover on k-uniform k-partite hypergraphs, and prove a nearly optimal 
NP-hardness of approximating it within k/2-1, where a 
k/2-approximation is known due to Lovász. 


The results in this talk are based on joint works with Sanjeev Arora, 
Rong Ge, Lorenzo Orecchia, Rishi Saket, Grant Schoenebeck, Madhur 
Tulsiani, and Nisheeth K. Vishnoi. 

​ 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/talks/attachments/20130307/c12cb667/attachment.html>