Anuradha Venugopalan will present her research seminar/general exam on Wednesday May 19 at 2PM in Room 402. The members of her committee are: Sanjeev Arora (advisor), Moses Charikar, and Bob Tarjan. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. --------------------------------------------- Title: Investigating the 3-coloring and Vertex Cover problems Abstract: Mathematical programs and their hierarchies are currently the most commonly used approaches for approximating most combinatorial optimization problems. I shall talk about the existing SDP based algorithms for the coloring and Vertex Cover problems and show instances where these algorithms do not work well. In search of better algorithms for these problems, I shall make some observations about these instances. A recent work by Arora, Barak and Steurer offers better approximation guarantees than the SDP methods for some optimization problems including vertex cover. However, their algorithm uses time exponential in the threshold rank, that is, the number of 'large' eigenvalues of the graph. I shall show bounds on the threshold rank of the instances where the SDPs perform poorly and examine how the new algorithm performs on them. Reading List: -Unique Games on Expanding Constraint Graphs are Easy. : Arora Khot Kolla Steurer Tulsiani Vishnoi '08 -A 2^n^poly(\epsilon)-time Algorithm for Unique Games. : Arora Barak Steurer '10 -New Approximation Guarantee for Chromatic Number. : Arora Chlamtac Charikar '06 -Improved Approximation Guarantees Through Higher Levels of SDP Hierarchies. : Chlamtac Singh '08 -Optimal inapproximability results for max-cut and other 2-variable csps? : Khot Kindler Mossel O'Donnell '07 -SDP Integrality Gaps with Local l_1-Embeddability. : Khot Saket '09 -On semidefinite programming relaxations for graph coloring and vertex cover. : Charikar '02 -Integrality Gaps for Sherali-Adams Relaxations. : Charikar Makarychev Makarychev '09 -Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. : Alekhnovich Arora Tourlakis '05 -On the optimality of the random hyperplane rounding technique for max cut. : Feige Schechtman '02 -On the concentration of eigenvalues of random symmetric matrices. : Alon Krivelevich Vu '02 -A better approximation ratio for the Vertex Cover problem. : George Karakostas '05 -Computational Complexity: A modern approach. Chapters: 1-8 and the PCP chapters. : Arora Barak