Rajsekar Manokaran will present his preFPO on Wednesday March 28 at 1:30PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark Braverman and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------- Title: Approximability using Mathematical Relaxations A standard approach to coping with the NP-hardness of a combinatorial optimization problem involves designing algorithms that guarantee a solution within a factor p of the optimum (a.k.a an p-approximation algorithm). We study the approximability of various fundamental graph optimization problems using linear programming~(LP) relaxations. In the first part of the thesis, we study simple LP relaxations for Metric Labeling, and a variety of Packing and Covering problems. For all these problems, we show that the relaxation already obtains the best approximation, upto known algorithmic barriers. The novelty here is the generality of the technique: the proof only uses simple "local" properties of the relaxation, oblivious of the actual approximation factor, p, obtained thus. In the second part, we use insights obtained from the above in studying the approximability of a large class of ordering problems, including the Maximum Acyclic Subgraph problem. Here, we show that a trivial algorithm, that outputs a random ordering irrespective of the instance in hand, already achieves the best appromximation factor upto known algorithmic techniques. In the final part, we study implications of "average-case" algorithmic barriers. In particular, we show that the densest-k-subgraph problem is hard to approximate to within any constant factor assuming random k-AND formulas are hard to distinguish from well satisfiable ones. These results are based on joint works with Noga Alon, Sanjeev Arora, Moses Charikar, Venkatesan Guruswami, Johan Hastad, Amit Kumar, Dana Moshkovitz, Joseph Naor, Prasad Raghavendra, Roy Schwartz, Madhur Tulsiani, Nisheeth Vishnoi and Omri Weinstein