Aravindan Vijayaraghavan will present his preFPO on Wednesday March 7 at 11AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and Mark Braverman, readers; David Blei and Konstantin Makarychev, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- Understanding Approximability through Average-case Analysis We study the approximability of fundamental graph optimization problems through approximation algorithms for both realistic average-case and worst-case instances of problems. We study average-case instances to shed new light on approximability in two ways : 1. designing better algorithms for realistic average-case instances. 2. designing new algorithms with better guarantees even in worst-case, and identifying new barriers for further progress. In the first part of the thesis, we study Graph partitioning problems which are ubiquitous in computer science and form a central topic of study. However, constant factor approximations have been elusive. Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for realistic average case instances? We study a semi-random model for graph partitioning problems, that is more general than previously studied random models, and that seems to capture many real-world instances well. We design new O(1) approximation algorithms for classical graph partitioning problems like Balanced Separator, Sparsest cut, Multicut and Small set expansion for these semi-random instances. Our algorithms are based on new SDP-based techniques and work in a wider range of parameters than algorithms for previously studied random and semi-random models. In the second part, we show how insights from algorithms for a natural average-case version are used to obtain new worst-case approximation algorithms for the Densest k-Subgraph problem -- an important yet poorly understood problem in combinatorial optimization. The counting-based algorithms for the average-case version of the problem are translated to algorithms for the worst-case using linear programming hierarchies: this gives an improved n^{1/4} factor approximation. Studying the average-case version also points to a concrete barrier for further progress on approximations for Densest k-subgraph. These results are based on joint works with Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Venkatesan Guruswami, Konstantin Makarychev, Yury Makarychev and Yuan Zhou.