[talks] A Vijayaraghavan preFPO

[Melissa M. Lawson]

Aravindan Vijayaraghavan will present his preFPO on 
Wednesday March 7 at 11AM in Room 302 (note room).  The 
members of his committee are:  Moses Charikar, advisor; 
Sanjeev Arora and Mark Braverman, readers; David Blei 
and Konstantin Makarychev, nonreaders.  Everyone is invited
to attend his talk.  His abstract follows below.
----------------------

Understanding Approximability through Average-case Analysis

We study the approximability of fundamental graph optimization problems through
approximation algorithms for both realistic average-case and
worst-case instances of problems.
We study average-case instances to shed new light on approximability
in two ways :
1. designing better algorithms for realistic average-case instances.
2. designing new algorithms with better guarantees even in worst-case, and
    identifying new barriers for further progress.

In the first part of the thesis, we study Graph partitioning problems
which are ubiquitous in computer science and form a central topic of
study. However, constant factor approximations have been elusive.
Since real-world instances are unlikely to behave like worst-case
instances, a compelling question is :
can we design better algorithms for realistic average case instances?

We study a semi-random model for graph partitioning problems, that is
more general than previously studied random models, and that seems to 
capture many real-world instances well. We design new O(1) approximation 
algorithms for classical graph partitioning problems like Balanced Separator,
Sparsest cut, Multicut and Small set expansion for these semi-random
instances. Our algorithms are based on new SDP-based techniques and
work in a wider range of parameters than algorithms for previously
studied random and semi-random models.

In the second part, we show how insights from algorithms for a natural
average-case version are used to obtain new worst-case approximation 
algorithms for the Densest k-Subgraph problem -- an important yet poorly 
understood problem in combinatorial optimization. The counting-based algorithms 
for the average-case version of the problem are translated to algorithms for 
the worst-case using linear programming hierarchies: this gives
an improved n^{1/4} factor approximation. Studying the average-case
version also points to a concrete barrier for further progress on
approximations for Densest k-subgraph.

These results are based on joint works with Aditya Bhaskara, Moses
Charikar, Eden Chlamtac, Uriel Feige, Venkatesan Guruswami, Konstantin
Makarychev, Yury Makarychev and Yuan Zhou.