Sanjeev Arora's Selected Publications

Grouping by Topic:

1. Surveys
2. Approximation Schemes for Geometric NP-hard Problems
3. Other approximation algorithms.
4. Probabilistically checkable proofs and other areas.
5. Other topics.
6. Geometric Embeddings
7. Course notes, writings

Surveys/Thesis:

1. The Approximability of NP-hard problems.
           Sanjeev Arora
          Survey based upon a plenary lecture at ACM STOC'98.
         [ Postscript ]

2. Hardness of Approximations.
           Sanjeev Arora and Carsten Lund.
   In Approximation Algorithms for NP-hard Problems, Dorit Hochbaum, Ed.  
   PWS Publishing , 1996.
   [Postscript ] ( This work is copyrighted by PWS Publishing, with all rights reserved. )

3. Probabilistic checking of proofs and the hardness of approximation problems.
           Sanjeev Arora.
           Ph.D. Thesis, UC Berkeley, 1994. This thesis was a cowinner of the ACM Doctoral Dissertation award, 1995.
           [Postscript]  [pdf]
   
4. Around the PCP Theorem: Six Lectures.
           Sanjeev Arora. (From McGill Workshop on Complexity Theory, Barbados,
           1996. Most lectures are not about the PCP Theorem.)
            [Postscript]
5. Approximation schemes for NP-hard geometric optimization problems: A survey.
           Sanjeev Arora. This survey accompanied a semiplenary talk at ISMP
            and appeared in Math Programming, 97 (1,2) July 2003.
           [Postscript] 
   
6. Multiplicative weights method: a meta-algorithm and its applications. (A survey)
   Sanjeev Arora, Elad Hazan, and Satyen Kale. [pdf] Accepted to Theory of Computing journal, 2010.
   
7. Geometry, Flows, and Graph Partitioning Algorithms. (Invited survey)
   Sanjeev Arora, Satish Rao, and Umesh Vazirani. Communications of ACM,  Oct 2008. [pdf]
         

Approximation schemes for geometric NP-hard problems:

1. Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems.
          Sanjeev Arora.
          Journal of the ACM 45(5) 753-782, 1998..
          [Postscript of journal version].
          (This paper is based upon two conference paper. The [ first ] in IEEE FOCS 1996
           pp 2--13 and the [second ] in  IEEE FOCS 1997. If you wish to impelement this
            algorithm, I suggest testing trying it on the TSPLIB database. )
         
2. Polynomial Time Approximation Schemes for Euclidean k-medians and related problems. 
           Sanjeev Arora, Prabhakar Raghavan, and Satish Rao.
            In ACM STOC'98. 
            [ Postscript ]
3. Polynomial time approximation scheme for Weighted Planar Graph TSP.
          Sanjeev Arora, Mic Grigni, David Karger, Philip Klein, Andrzej Woloszyn .
           Proc. SIAM SODA, 1998.
           [ Postscript]
4. Approximations schemes for degree-restricted MST and Red-Blue separation problem.
         Sanjeev Arora and Kevin L. Chang.
          In Proc. ICALP 2003. [Postscript of journal version.]

Other Approximation Algorithms:

1. Page Replacement for general caching problems.
          Susanne Albers, Sanjeev Arora, Sanjeev Khanna.
          Proc. SIAM SODA, 1999.
          [Postscript]
2. A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems.
          Sanjeev Arora, Alan Frieze, and Haim Kaplan. IEEE FOCS'96 pp 24-33.
          Final version in Math Programming.
         [ Postscript ]
3. Polynomial Time Approximation Schemes for dense instances of graph problems.
         Sanjeev Arora, David Karger, and Marek Karpinski.  ACM Symposium on Theory of Computing,  
         1995. Final version in Journal of Computer and System Sciences. 
         [ postscript ]
4. Approximation schemes for minimum latency problems.
         Sanjeev Arora and George Karakostas. Proc. ACM STOC 1999.
         [ postscript ]
5. A 2+epsilon approximation for the k-MST problem.
          Sanjeev Arora and George Karakostas. Proc. SIAM Symp. Discrete Algorithms (SODA) 2000.
          [ postscript ]
6. Expander Flows, Geometric Embeddings, and Graph Partitionings.
          Sanjeev Arora, Satish Rao, and Umesh Vazirani. ACM Symposium on Theory of Computing, 2004.
          (This paper shared the best paper award at this conference.)
          [postscript of conference version][pdf]
          [pdf of more complete version]
7. O(\sqrt{log n}) approximation to SPARSEST CUT in O(n^2) time.
        Sanjeev Arora, Elad Hazan, and Satyen Kale.
         Proc. IEEE Foundations of Computer Science, 2004.
        Paper can be found here.
8. New approximation guarantees for Chromatic Number.
      Sanjeev Arora,  Moses Charikar, Eden Chlamtac.
      Proc. IEEE Foundations of Computer Science 2006.  Paper can be found here.
9. A combinatorial, primal-dual approach to solving SDPs.
    Sanjeev Arora, Satyen Kale.
    Proc. ACM STOC 2007. pdf file of more complete version.
10. Unique Games on Expanding Constraints Graphs are Easy
    Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steuer, Madhur Tulsiani, and
    Nisheeth Vishnoi. Proc. ACM STOC 2008. pdf.
    
11. Subexponential algorithms for Unique Games and Related Problems. pdf
    Sanjeev Arora, Boaz Barak, David Steurer, Proc IEEE FOCS 2010. (cowinner of Best Paper award.)
    
    

Probababilistically Checkable Proofs and Related Topics:

1. Improved Low-Degree Testing and its Applications.
            Sanjeev Arora and Madhu Sudan. In ACM STOC 1997.
            [ Postscript ]
2. Reductions, Codes, PCPs and Inapproximability. (Included here for historical interest;
             Hastad's subsequent results make the musings here obsolete.)
            Sanjeev Arora.
            IEEE Foundations of Computer Science, pages 404-413, 1995.
           [ Postscript ]
3. Hardness of Approximate Optima in Lattices, Codes, and Linear Systems. 
           Sanjeev Arora, Laszlo Babai, Jacques Stern and Z Sweedyk. 
           IEEE Foundations of Computer Science, 1993.   Final version in Journal of Computer and System           Sciences, 54(2):317--331, 1997.
           [ postscript ]
4. Proof Verification and Hardness of Approximation Problems.
             Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan and Mario Szegedy. 
             Journal of ACM, 45(3):501-555, 1998. Prelim. version in IEEE Foundations of Computer Science, 1992.
             [ Postscript ]  (This paper was a co-winner of the ACM-EATCS Goedel Prize 2001.)
5. Probabilistic Checking of Proofs: A New Characterization of NP.
         Sanjeev Arora and Muli Safra.
          Journal of ACM, 45(1):70--122, 1998. Prelim. version in IEEE Foundations of Computer
               Science, 1992.
   [ Postscript ]   (This paper was a co-winner of the ACM-EATCS Goedel Prize 2001.)

Other topics:

1. Simulating Quadratic Dynamical Systems is PSPACE-complete. 
   Sanjeev Arora, Yuval Rabani, and Umesh Vazirani.  ACM Symposium on Theory of Computing, 1994.
   [ postscript ]
2. Online Algorithms for Path-selection in a Nonblocking Network.
     Sanjeev Arora, Tom Leighton, and Bruce Maggs.
     SIAM Journal on Computing, Vol. 25, No. 3, June 1996, pp. 600-625. (Prelim.
   version in Proc. ACM Symposium on Theory of Computing, 1990.)
   [ pdf]
3. A polynomial time algorithm to learn a mixture of general gaussians.
   Sanjeev Arora and Ravi Kannan.
   ACM Symposium on Theory of Computing, 2001.
   [ postscript ]
   Final version in Annals of Applied Probability.   [journal version(pdf version)]
4. An optimal online algorithm for a bandwidth utilization problem.
     Sanjeev Arora and William Brinkman.
     ACM-SIAM Symposium on Discrete Algorithms, 2002. [ postscript ]
   [Journal version] (To appear in Journal of Scheduling, Special issue on SODA 2002.)
5. Fitting algebraic curves to Noisy Data.
     Sanjeev Arora and Subhash Khot.
     ACM Symposium on Theory of Computing, 2002.
     [ postscript ] [Journal version] to appear in special issue of JCSS on STOC 2002.
6. Proving integrality gaps without knowing the linear program.
   Sanjeev Arora, Bela Bollobas and Laszlo Lovasz.
   Proc. IEEE Foundations of Computer Science, 2002. [postscript]
   Journal version in Theory of Computing, 2008.
   
7. Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.
   Misha Alekhnovich, Sanjeev Arora, Iannis Tourlakis.
   ACM Symposium on Theory of Computing, 2005. [pdf] [Journal version]
   
8. Fast approximation algorithms for semidefinite programming using the multiplicative weights method.
   Sanjeev Arora, Elad Hazan, Satyen Kale.
   IEEE Foundations of Computer Science, 2005. [pdf]
9. Message-Passing Algorithms and Improved LP Decoding.
   Sanjeev Arora, David Steuer, and Constantinos Daskalakis. ACM STOC 2009. pdf.
   
10. Towards a study of low-complexity graphs
    Sanjeev Arora, David Steurer, and Avi Wigderson. ICALP 2009. pdf.
11. Computational complexity and informational asymmetry in financial products.
    Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge.
    Working paper 2009.  pdf Shorter version in Proc. Innovations in CS, 2010.
    CACM version (invited contribution) and a brief introduction by David Parkes.
    
12. New algorithms for learning in presence of Errors.
    Sanjeev Arora and Rong Ge, Proc. ICALP 2010. (ECCC version)
13. New tools for graph coloring.
    Sanjeev Arora and Rong Ge, Proc. APPROX 2011. Arxiv version.
14. Computing a nonnegative matrix factorization--Provably.
    Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra.
    To appear in Proc. STOC 2012. arxiv version.
    

Geometric embeddings of finite metric spaces

1. Euclidean distortion and the sparsest cut.
   Sanjeev Arora, James Lee, and Assaf Naor.
   ACM Symposium on Theory of Computing, 2005. 
   Journal version in J. Amer. Math Soc., No. 1, pp 1--21, 2008. pdf
   
2. Local versus global properties of metric spaces.
   Sanjeev Arora, Laszlo Lovasz, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala.
     Proc. ACM SIAM SODA 2006 [pdf]

Course Notes etc.

1. Lecture notes on complexity theory from Spring 2001 are here. A single postscript file
   containing all the lecture notes is here.
2. Lecture notes from three lectures titled "Exploring complexity using reductions." Given at
   the IAS-Park City. Postscript file.
3. Lecture notes from A Theorist's Toolkit (Fall'02) are here.
4. Lecture notes from a grad course (Spring'05) on  Algorithms and Complexity.
5. Lecture plan and notes from a grad course in Advanced Algorithms.
   (Fall 2005) My stab at how to teach grad algorithms so as to prepare students
   for research in this every-broadening field. See also the 2006 and 2008 offerings.
   
6. A course for nonmajors (usually social science and humanities majors) called
   The Computational Universe.