[talks] A Bhaskara general exam

[Melissa Lawson]

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).