[talks] A Bhaskara preFPO

[Melissa M. Lawson]

Aditya Bhaskara will present his preFPO on Monday April 2 
at 1PM in Room 301. His committee is:  Moses Charikar, advisor; 
Sanjeev Arora and Zeev Dvir, readers; Bernard Chazelle and 
Amit singer (Math), nonreaders.  Everyone is invited to attend 
his talk.  His abstract follows below.

Title: Finding Dense Sub-structures in Graphs and Matrices

A basic primitive in graph optimization is that of finding small induced subgraphs of a given graph with ``many'' edges.  Questions of this nature arise often in practice, for instance in finding ``communities'' in social networks, and in clustering type problems. From the theory side, this captures questions such as ``small-set expansion'', which has proved to be an intriguing open problem.

A simple formalization we study is the Densest-k-subgraph problem, where the objective, given a graph G, is to find an induced subgraph on k vertices with as many edges as possible. There is a vast gap in our understanding of this problem in terms of the approximation ratio we can achieve. I will discuss the state of the art in approximation algorithms, and try to point out why it is difficult to write convex programming relaxations for the problem. This is akin to difficulties that arise in other problems which have a ``small-support'' constraint, such as those arising in compressed sensing. An interesting aspect of the densest-k-subgraph problem is that random instances seem to be the hardest for obtaining approximation algorithms.

A question related to this is that of computing the q->p (operator) norm of a matrix. Such norms are generalizations of singular values, and in general, computing them is not a convex optimization problem. We will see conditions under which it is possible to compute them efficiently, and attempt to obtain a `characterization', by complementing this with hardness results.

We also study generalizations of singular values to three-dimensional tensors, a problem which arises in applications involving 3D data. The question is believed to be very hard (even to approximate) in general. We study the following `planted' variant: suppose we know that the tensor is "rank-k + small noise" (but we do not have access to such a decomposition), then can we solve the tensor analog of largest singular value? We show that this can be done in time exponential in $k$ (but almost linear in the size of the tensor).

Results in the talk will be based on joint works with Sanjeev Arora, Moses Charikar, Eden Chlamtac, Uriel Feige, Ravi Kannan, and Aravindan Vijayaraghavan.