Rajsekar Manokaran will present his research seminar/general exam on Monday May 5 at 2PM in Room 402. The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and Boaz Barak. Everyone is welcome to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list appear below. Abstract -------- Mathematical relaxations are one of the most powerful tools used in designing approximation algorithms for hard combinatorial optimization problems. For example, linear programming relaxations have provided the best approximation algorithms known for a huge number of optimization problems. More recently, for some optimization problems, semidefinite relaxations have been used to obtain breakthrough improvements in the approximation factor. This work investigates the limits on approximations achieved by mathematical relaxations of combinatorial optimization problems and their relation to the computation hardness of approximating them. For a small yet quite general set of problems, a direct way to convert integrality gaps for a linear programming relaxation of the problem into a computational hardness result under a certain conjecture is shown. This problem, known as metric labeling is a generalization of classification problems with pairwise constraints. In this work, it is shown that a certain linear programming relaxation gives the best approximation one can expect, assuming the unique games conjecture. Continuing in the same theme, a similar computational hardness result is shown for the maximum acyclic subgraph problem. Here, a trivial algorithm obtains a half approximation and obtaining a better approximation algorithm has been an open problem for quite some time. Assuming the UG conjecture, this work shows that it is computationally hard to approximate the maximum acyclic subgraph problem by a better factor is hard. This result also, unconditionally, rules out a simple semi-definite programming approach to obtain a better approximation. Reading List ------------ 1. Complexity Theory: A Modern Approach by Sanjeev Arora and Boaz Barak Chapters 1-8, 16-19. 2. Approximation Algorithms by Vijay Vazirani Chapters 1-4, 12-21. 3. Expander Flows, Geometric Embeddings, and Graph Partitionings by Sanjeev Arora, Satish Rao, and Umesh Vazirani ACM Symposium on Theory of Computing, 2004. 4. A tight bound on approximating arbitrary metrics by tree metrics by Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar ACM Symposium on Theory of Computing, 2003 5. Some Optimal Inapproximability Results by Johan Hastad STOC 1997. 6. Proving integrality gaps without knowing the linear program. by Sanjeev Arora, Bela Bollobas and Laszlo Lovasz. Proc. IEEE Foundations of Computer Science, 2002. 7. Local Global Tradeoffs in Metric Embeddings, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, FOCS 2007, pp. 713-723. 8. On the power of unique 2-prover 1-round games by Subhash Khot STOC '02. 9. Optimal inapproximability results for max-cut and other 2-variable csps? by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. FOCS '04. 10. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into $L_1$. by Subhash Khot and Nisheeth Vishnoi. FOCS '05. 11. Noise stability of functions with low influences: Invariance and optimality. by Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz. FOCS '05. 12. Vertex cover might be hard to approximate to within 2-$\epsilon$. by Subhash Khot and Oded Regev. J. Comput. Syst. Sci. 13. Near-Optimal Algorithms for Unique Games, by Moses Charikar, Konstantin Makarychev, Yury Makarychev, STOC 2006, pp. 205-214. 14. Approximation algorithms for the metric labeling problem via a new linear programming formulation. Chandra Chekuri, Sanjeev Khanna, Joseph (Seffi) Naor, and Leonid Zosin. SIAM J. Disc. Math. 15. On the advantage over random for maximum acyclic subgraph. Moses Charikar, Konstantin Makarychev, and Yury Makarychev. FOCS 2007, pp. 625-633.