[talks] A Vijayaraghavan general exam

[Melissa Lawson]

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