Aravindan Vijayaraghavan will present his research seminar/general exam on Friday May 15 at 2PM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, and Boaz Barak. Everyone is invited 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 follow below. ------------------------------------------------------------------------------------------ --------------------------------------------------- Abstract Many approximation algorithms proceed by finding a good partial solution and then recursing into a sub-instance to find the remaining solution. With this motivation, we study the problem of maximizing certain integer quadratic programs with a ratio objective. We first consider the Max-cut gain problem where the objective is to find a cut which maximizes the advantage over the random assignment, of the fraction of edges cut. Trevisan recently gave an algorithm, that uses just the eigenvector corresponding to the smallest eigenvalue (\lambda), which given a gain of G, obtains a cut with an exponentially small cut-gain ( exp(-1/ G)). He considers the 'gain ratio' (gain achieved by partial cuts i.e cuts (L,R) of a subset S of vertices) and obtains a exponential small gain-ratio (~ exp(-1/|\lambda|) ) and then progresses recursively. He further conjectures that a much better gain-ratio of \Omega(|\lambda|/log(|\lambda|)), which matches the SDP algorithm of Charikar-Wirth, is achievable. However, we refute this conjecture, by showing that the gain-ratio achieved by his algorithm is almost tight, thus showing that eigen-value based methods can only produce cuts with exponentially small gain (and gain-ratio). We then consider the ratio version of a general quadratic the program i.e maximize ratio of \sum_{ij} a_{ij}x_i x_j to the number of non-zero x_i values (where x_i can take values in {-1,0,1}). We strengthen the natural SDP relaxation with some additional constraints (similar to triangle inequalities) and give a rounding algorithm which obtains an approximation ratio of O(n^{1/3}). We also show an integrality gap of \Omega(n^{1/4}) for this stronger relaxation. (Based on joint work with Moses Charikar and Aditya Bhaskara) Reading list: Books/Surveys: 1. Approximation Algorithms by V.Vazirani - chapters 1-6, 12-21 2. Hoory, Linial, Wigderson. Expander graphs and their applications. (Chapters 2,3,4,7) 3. Arora, Barak. Complexity Theory: A Modern Approach. (PCP Chapters, 11,21,22) Research articles: 1. Luca Trevisan. Maxcut and the smallest eigenvalue. 2. Charikar, Wirth. Maximizing Quadratic programs:Extending the Groethendieck's inequality. 3. Alon, Naor. Approximating the Cut-Norm via Grothendieck's Inequality 4. Khot, O'Donnell. SDP gaps and UGC-hardness for Max-Cut-Gain 5. Khot, Kindler, Mossel, O'Donnell. Optimal inapproximability results for MAX-CUT and other two-variable CSPs? 6. Feige, Kortsartz, Peleg. The Dense k-subgraph problem. 7. Feige. Relations between average case complexity and approximation complexity 8. Feige, Selster. On the densest k-subgraph problem. 9. Alon, Krivelevich, Sudakov. Finding a large hidden clique in a random graph 10. Charikar, Makarychev, Makarychev. Near-optimal algorithms for unique games. 11. Charikar, Markarychev, Makarychev. Integrality Gaps for Sherali-Adams Relaxations. 12. Raecke. Optimal Hierarchical Decompositions for Congestion minimization in networks 13. Fakcharoenphol, Rao, Talwar. A tight bound on approximating arbitrary metrics by tree metrics 14. Arora, Khot, Kolla, Steurer, Tulsiani and Vishnoi. Unique Games on Expanding Constraint Graphs are Easy