Grouping
by Topic:
 Surveys
 Approximation
Schemes
for
Geometric
NPhard Problems
 Other
approximation
algorithms.
 Probabilistically
checkable
proofs
and
other areas.
 Other
topics.
 Geometric
Embeddings
 Course
notes, writings


Surveys/Thesis:
 The Approximability of
NPhard
problems.
Sanjeev
Arora
Survey based
upon a plenary
lecture at ACM STOC'98.
[ Postscript ]
 Hardness of
Approximations.
Sanjeev Arora and Carsten Lund.
In Approximation Algorithms for NPhard
Problems, Dorit
Hochbaum, Ed.
PWS Publishing ,
1996.
[Postscript ] (
This work is
copyrighted by PWS Publishing, with all rights
reserved. )
 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]
 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]
 Approximation schemes
for NPhard
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]
 Multiplicative
weights
method:
a metaalgorithm and its applications. (A
survey)
Sanjeev Arora, Elad Hazan, and Satyen Kale. [pdf]
Accepted to Theory of Computing journal, 2010.
 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 NPhard problems:
 Polynomialtime
Approximation
Schemes for Euclidean TSP and other Geometric
Problems.
Sanjeev
Arora.
Journal
of the
ACM 45(5) 753782, 1998..
[Postscript
of journal version].
(This paper
is based upon two
conference paper. The [
first ] in IEEE
FOCS 1996
pp
213 and the [second ]
in IEEE FOCS 1997. If you wish
to impelement this
algorithm, I suggest
testing trying it on the TSPLIB
database. )
 Polynomial Time
Approximation
Schemes for Euclidean kmedians and related
problems.
Sanjeev
Arora,
Prabhakar
Raghavan, and Satish Rao.
In ACM STOC'98.
[
Postscript ]
 Polynomial time
approximation
scheme for Weighted Planar Graph TSP.
Sanjeev
Arora,
Mic
Grigni,
David Karger, Philip Klein, Andrzej Woloszyn .
Proc.
SIAM SODA, 1998.
[
Postscript]
 Approximations schemes
for
degreerestricted MST and RedBlue separation
problem.
Sanjeev
Arora and Kevin L. Chang.
In Proc.
ICALP 2003. [Postscript of
journal version.]
Other Approximation
Algorithms:
 Page Replacement for
general
caching problems.
Susanne
Albers,
Sanjeev Arora, Sanjeev Khanna.
Proc. SIAM
SODA, 1999.
[Postscript]
 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 2433.
Final version
in Math Programming.
[ Postscript ]
 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 ]
 Approximation schemes
for minimum
latency problems.
Sanjeev
Arora
and George Karakostas. Proc. ACM STOC 1999.
[ postscript ]
 A 2+epsilon
approximation for the
kMST problem.
Sanjeev Arora
and George
Karakostas. Proc. SIAM Symp. Discrete Algorithms
(SODA) 2000.
[ postscript ]
 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]
 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.
 New approximation
guarantees for Chromatic
Number.
Sanjeev Arora, Moses
Charikar, Eden Chlamtac.
Proc. IEEE Foundations of Computer
Science 2006.
Paper can be found here.
 A combinatorial,
primaldual approach to
solving SDPs.
Sanjeev Arora, Satyen Kale.
Proc. ACM STOC 2007. pdf file of more
complete version.
 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.
 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:
 Improved LowDegree
Testing and
its Applications.
Sanjeev Arora and
Madhu Sudan. In ACM STOC 1997.
[
Postscript ]
 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 404413, 1995.
[ Postscript ]
 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):317331, 1997.
[ postscript ]
 Proof Verification and
Hardness
of Approximation Problems.
Sanjeev Arora,
Carsten Lund, Rajeev Motwani, Madhu Sudan and
Mario Szegedy.
Journal of ACM, 45(3):501555, 1998.
Prelim. version in
IEEE Foundations of Computer Science, 1992.
[ Postscript ]
(This paper was a
cowinner of the ACMEATCS
Goedel
Prize
2001.)
 Probabilistic Checking
of Proofs:
A New Characterization of NP.
Sanjeev
Arora
and Muli Safra.
Journal of
ACM, 45(1):70122,
1998.
Prelim.
version in IEEE Foundations of Computer
Science,
1992.
[ Postscript ]
(This paper was a
cowinner of the ACMEATCS
Goedel
Prize
2001.)
Other
topics:
 Simulating Quadratic
Dynamical
Systems is PSPACEcomplete.
Sanjeev Arora, Yuval Rabani, and Umesh
Vazirani. ACM
Symposium on Theory of Computing, 1994.
[ postscript ]
 Online Algorithms for
Pathselection in a Nonblocking Network.
Sanjeev Arora, Tom
Leighton, and
Bruce Maggs.
SIAM Journal on Computing, Vol.
25, No. 3, June 1996,
pp. 600625. (Prelim.
version in Proc. ACM Symposium on Theory of
Computing, 1990.)
[ pdf]
 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)]
 An optimal online
algorithm for a
bandwidth utilization problem.
Sanjeev Arora and
William
Brinkman.
ACMSIAM Symposium on Discrete
Algorithms, 2002. [ postscript ]
[Journal
version] (To appear in
Journal of Scheduling, Special issue on SODA
2002.)
 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.
 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.
 Towards strong nonapproximability results in
the
LovaszSchrijver hierarchy.
Misha Alekhnovich, Sanjeev Arora, Iannis
Tourlakis.
ACM Symposium on Theory of Computing, 2005. [pdf] [Journal
version]
 Fast
approximation
algorithms for semidefinite programming using
the multiplicative
weights method.
Sanjeev Arora, Elad Hazan, Satyen Kale.
IEEE Foundations of Computer Science, 2005. [pdf]
 MessagePassing
Algorithms
and Improved LP Decoding.
Sanjeev Arora, David Steuer, and Constantinos
Daskalakis. ACM STOC
2009. pdf.
 Towards a study
of
lowcomplexity graphs
Sanjeev Arora, David Steurer, and Avi Wigderson.
ICALP 2009. pdf.
 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.
 New algorithms
for learning in presence of Errors.
Sanjeev Arora and Rong Ge, Proc. ICALP 2010. (ECCC
version)
 New tools for
graph coloring.
Sanjeev Arora and Rong Ge, Proc. APPROX 2011. Arxiv
version.
 Computing a
nonnegative matrix factorizationProvably.
Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra.
To appear in Proc. STOC 2012. arxiv
version.
Geometric embeddings of
finite
metric spaces
 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
121, 2008.
pdf
 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.
 Lecture notes on complexity
theory from
Spring 2001 are
here. A single postscript file
containing all the lecture notes is here.
 Lecture notes from three
lectures titled
"Exploring complexity using reductions." Given at
the IASPark City. Postscript
file.
 Lecture notes from A
Theorist's
Toolkit (Fall'02) are
here.
 Lecture notes from a grad
course
(Spring'05) on Algorithms
and
Complexity.
 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 everybroadening field. See
also the 2006
and 2008
offerings.
 A course for nonmajors
(usually social
science and humanities majors) called
The
Computational
Universe.
