Aditya Bhaskara will present his research seminar/general exam on Thursday May 14 at 10AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor, Sanjeev Arora, and Bob Tarjan. 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 -------- We will look at the densest-k-subgraph (DkS) problem: Given a graph G(V,E) and a parameter k, find a set of k vertices such that the number of edges among them is maximized. The problem is quite well-studied, but there is a big gap between the known algorithms and inapproximability results. There are combinatorial (greedy, path-based), and SDP based approaches known for the problem, which do well in different ranges of the parameters (degree, k). A common barrier for these approaches is the case of random graphs G(n,p) with planted dense subgraphs of size $k$. We thus propose and study a "Dense-vs-Random" problem: Distinguish a random graph of degree \Delta from the class of graphs with a k-subgraph of density (average degree) d. The question is to find the smallest $d$ for which this is possible (in terms of n, \Delta). For random graphs of degree n^{q} (0 < q < 1), we design algorithms that distinguish them from graphs with k-subgraphs of average degree >> k^q. The idea is to do an appropriate "local" counting. Interestingly, for such local counting, k^q seems to be a barrier, while a simple SDP based approach does better when q < 1/2. The main contribution is to use these "local structures" in obtaining algorithms for dense k-subgraph. We show how to do this for structures of certain special kinds. It seems reasonable to conjecture that this can be done with all structures. Doing this would imply an n^{1/4} approximation algorithm for dense k-subgraph. Our current techniques allow us to obtain a slightly worse ratio of n^{3/11}. It is an interesting question to go beyond n^{1/4} -- this is the limit for both the SDP and the local counting approaches. (Joint work with Moses Charikar and Aravindan Vijayaraghavan) Reading list ------- ---- N. Alon, M. Krivelevich and B. Sudakov, Finding a large hidden clique in a random graph, Random Structures and Algorithms 13 (1998), 457-466. Frank McSherry, Spectral Partitioning of Random Graphs. Proceedings of FOCS 2001, 529-537. Moses Charikar and Anthony Wirth, Maximizing Quadratic Programs: Extending Grothendieck's Inequality. Noga Alon and Assaf Naor, Approximating the cut-norm via Grothendieck's inequality. Luca Trevisan, Max Cut and the Smallest Eigenvalue. Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani and Nisheeth K. Vishnoi, Unique games on expanding constraint graphs are easy. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Near-Optimal Algorithms for Unique Games. Uriel Feige, Relations between Average Case Complexity and Approximation Complexity. U. Feige and M. Seltser, On the densest $k$-subgraph problems. Moses Charikar, Konstantin Makarychev and Yury Makarychev, Integrality Gaps for Sherali-Adams Relaxations. Uri Feige and Robert Krauthgamer, The probable value of the Lovasz-Schrijver relaxations for maximum independent set. Tom Leighton and Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Sanjeev Arora, Satish Rao and Umesh Vazirani, Expander Flows, Geometric Embeddings, and Graph Partitionings. Books ----- Vijay Vazirani, Approximation Algorithms (Chapters 1-6, 12, 16, 19-22). Shlomo Hoory, Nati Linial, Avi Wigderson, Expander Graphs and their Applications (Chapters 1-4, 7). Sanjeev Arora, Boaz Barak, Computational Complexity: A modern approach (Chapters 1-11, 13, 21-22).