Sanjeev Arora

  1. A Reformulation of the Arora-Rao-Vazirani Structure Theorem.

    Authors: Sanjeev Arora, James Lee, Sushant Sachdeva
    Subjects: Discrete Mathematics
    Abstract

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

  2. Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes).

    Authors: 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
    Abstract

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

RSS-материал