Sanjeev Arora
A Reformulation of the Arora-Rao-Vazirani Structure Theorem.
Wed, 02/09/2011 - 16:01 — SomNambulAuthors: Sanjeev Arora, James Lee, Sushant Sachdeva
Subjects: Discrete Mathematics
AbstractIn a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log
n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut.
At the heart of their result is a geometric statement about sets of points that
satisfy triangle inequalities, which also underlies subsequent work on
approximation algorithms and geometric embeddings.In this note, we give an equivalent formulation of the Structure theorem in
[ARV] in terms of the expansion of large sets in geometric graphs on sets of
points satisfying triangle inequalities.Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes).
Tue, 02/23/2010 - 16:02 — SomNambulAuthors: Prahladh Harsha, David Pritchard, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, Gwen Spencer
Subjects: Computational Complexity
AbstractThese are the lecture notes for the DIMACS Tutorial "Limits of Approximation
Algorithms: PCPs and Unique Games" held at the DIMACS Center, CoRE Building,
Rutgers University on 20-21 July, 2009. This tutorial was jointly sponsored by
the DIMACS Special Focus on Hardness of Approximation, the DIMACS Special Focus
on Algorithmic Foundations of the Internet, and the Center for Computational
Intractability with support from the National Security Agency and the National
Science Foundation.
User login
