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. ​