Sanjeev Arora

	2009
64		Sanjeev Arora, David Steurer, Avi Wigderson: Towards a Study of Low-Complexity Graphs. ICALP (1) 2009: 119-131
63		Sanjeev Arora, Constantinos Daskalakis, David Steurer: Message passing algorithms and improved LP decoding. STOC 2009: 3-12
62		Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): (2009)
	2008
61		Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi: Unique games on expanding constraint graphs are easy: extended abstract. STOC 2008: 21-28
60		Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)
	2007
59		Sanjeev Arora, Satyen Kale: A combinatorial, primal-dual approach to semidefinite programs. STOC 2007: 227-236
58		Sanjeev Arora, James R. Lee, Assaf Naor: Fréchet Embeddings of Negative Type Metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)
	2006
57		Sanjeev Arora, Elad Hazan, Satyen Kale: A Fast Random Sampling Algorithm for Sparsifying Matrices. APPROX-RANDOM 2006: 272-279
56		Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local versus global properties of metric spaces. SODA 2006: 41-50
55		Sanjeev Arora, Eden Chlamtac: New approximation guarantee for chromatic number. STOC 2006: 215-224
54		Sanjeev Arora, George Karakostas: A 2 + epsilon approximation algorithm for the k-MST problem. Math. Program. 107(3): 491-504 (2006)
53		Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis: Proving Integrality Gaps without Knowing the Linear Program. Theory of Computing 2(1): 19-51 (2006)
	2005
52		Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs. FOCS 2005: 206-215
51		Sanjeev Arora, Elad Hazan, Satyen Kale: Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. FOCS 2005: 339-348
50		Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC 2005: 294-303
49		Sanjeev Arora, James R. Lee, Assaf Naor: Euclidean distortion and the sparsest cut. STOC 2005: 553-562
48		Sanjeev Arora, Bernard Chazelle: Is the thrill gone? Commun. ACM 48(8): 31-33 (2005)
47		Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs Electronic Colloquium on Computational Complexity (ECCC)(058): (2005)
	2004
46		Sanjeev Arora, Elad Hazan, Satyen Kale: 0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time. FOCS 2004: 238-247
45		Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231
44		Sanjeev Arora, Kevin L. Chang: Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems. Algorithmica 40(3): 189-210 (2004)
43		Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy Electronic Colloquium on Computational Complexity (ECCC)(117): (2004)
42		Sanjeev Arora, Bo Brinkman: A Randomized Online Algorithm for Bandwidth Utilization. J. Scheduling 7(3): 187-194 (2004)
	2003
41		Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai: Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003, Princeton, NY, USA, August 24-26, 2003, Proceedings Springer 2003
40		Sanjeev Arora: Proving Integrality Gaps without Knowing the Linear Program. FCT 2003: 1
39		Sanjeev Arora, Kevin L. Chang: Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. ICALP 2003: 176-188
38		Sanjeev Arora: How NP got a new definition: a survey of probabilistically checkable proofs CoRR cs.CC/0304038: (2003)
37		Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365-426 (2003)
36		Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. J. Comput. Syst. Sci. 67(2): 325-340 (2003)
35		Sanjeev Arora, George Karakostas: Approximation Schemes for Minimum Latency Problems. SIAM J. Comput. 32(5): 1317-1337 (2003)
	2002
34		Sanjeev Arora, Béla Bollobás, László Lovász: Proving Integrality Gaps without Knowing the Linear Program. FOCS 2002: 313-322
33		Eric Allender, Sanjeev Arora, Michael S. Kearns, Cristopher Moore, Alexander Russell: A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. NIPS 2002: 431-437
32		Sanjeev Arora, Bo Brinkman: A randomized online algorithm for bandwidth utilization. SODA 2002: 535-539
31		Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. STOC 2002: 162-169
	2001
30		Sanjeev Arora: Approximation Schemes for Geometric NP-Hard Problems: A Survey. FSTTCS 2001: 16-17
29		Sanjeev Arora, Ravi Kannan: Learning mixtures of arbitrary gaussians. STOC 2001: 247-257
	2000
28		Sanjeev Arora: Approximation algorithms that take advice. APPROX 2000: 1
27		Sanjeev Arora, George Karakostas: A 2+epsilon approximation algorithm for the k-MST problem. SODA 2000: 754-759
	1999
26		Susanne Albers, Sanjeev Arora, Sanjeev Khanna: Page Replacement for General Caching Problems. SODA 1999: 31-40
25		Sanjeev Arora, George Karakostas: Approximation Schemes for Minimum Latency Problems. STOC 1999: 688-693
24		Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. 58(1): 193-210 (1999)
	1998
23		Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn: A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. SODA 1998: 33-41
22		Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation Schemes for Euclidean k-Medians and Related Problems. STOC 1998: 106-113
21		Sanjeev Arora: The Approximability of NP-hard Problems. STOC 1998: 337-348
20		Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof verification and the hardness of approximation problems. Electronic Colloquium on Computational Complexity (ECCC) 5(8): (1998)
19		Sanjeev Arora, Shmuel Safra: Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM 45(1): 70-122 (1998)
18		Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and the Hardness of Approximation Problems. J. ACM 45(3): 501-555 (1998)
17		Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM 45(5): 753-782 (1998)
	1997
16		Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. FOCS 1997: 554-563
15		Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. RANDOM 1997: 55
14		Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. STOC 1997: 485-495
13		Sanjeev Arora, Madhu Sudan: Improved low-degree testing and its applications Electronic Colloquium on Computational Complexity (ECCC) 4(3): (1997)
12		Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk: The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations. J. Comput. Syst. Sci. 54(2): 317-331 (1997)
11		Sanjeev Arora, Ronald Fagin: On Winning Strategies in Ehrenfeucht-Fraïssé Games. Theor. Comput. Sci. 174(1-2): 97-121 (1997)
	1996
10		Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. FOCS 1996: 2-11
9		Sanjeev Arora, Alan M. Frieze, Haim Kaplan: A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems. FOCS 1996: 21-30
8		Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs: On-Line Algorithms for Path Selection in a Nonblocking Network. SIAM J. Comput. 25(3): 600-625 (1996)
	1995
7		Sanjeev Arora: Reductions, Codes, PCPs, and Inapproximability. FOCS 1995: 404-413
6		Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial time approximation schemes for dense instances of NP-hard problems. STOC 1995: 284-293
	1994
5		Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani: Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC 1994: 459-467
	1993
4		Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk: The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations FOCS 1993: 724-733
	1992
3		Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and Hardness of Approximation Problems FOCS 1992: 14-23
2		Sanjeev Arora, Shmuel Safra: Probabilistic Checking of Proofs; A New Characterization of NP FOCS 1992: 2-13
	1990
1		Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs: On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract) STOC 1990: 149-158

Coauthor Index

1	Susanne Albers	[26]
2	Mikhail Alecknovich	[43]
3	Michael Alekhnovich	[50]
4	Eric Allender	[33]
5	László Babai	[4] [12]
6	Eli Berger	[47] [52]
7	Béla Bollobás	[34] [53]
8	Bo Brinkman	[32] [42]
9	Kevin L. Chang	[39] [44]
10	Bernard Chazelle	[48]
11	Eden Chlamtac	[55]
12	Constantinos Daskalakis (Konstantinos Daskalakis)	[63]
13	Ronald Fagin	[11]
14	Alan M. Frieze	[9]
15	Michelangelo Grigni	[23]
16	Elad Hazan	[46] [47] [51] [52] [57]
17	Klaus Jansen	[41]
18	Satyen Kale	[46] [51] [57] [59]
19	Ravi Kannan (Ravindran Kannan)	[29]
20	Haim Kaplan	[9]
21	George Karakostas	[25] [27] [35] [54]
22	David R. Karger	[6] [23] [24]
23	Marek Karpinski	[6] [24]
24	Michael S. Kearns	[33]
25	Sanjeev Khanna	[26]
26	Subhash Khot	[31] [36] [61]
27	Guy Kindler	[47] [52]
28	Philip N. Klein	[23]
29	Alexandra Kolla	[61]
30	James R. Lee	[49] [58]
31	Frank Thomson Leighton (Tom Leighton)	[1] [8]
32	László Lovász	[34] [53] [56]
33	Carsten Lund	[3] [18] [20]
34	Bruce M. Maggs	[1] [8]
35	Cristopher Moore	[33]
36	Rajeev Motwani	[3] [18] [20]
37	Assaf Naor	[49] [58]
38	Ilan Newman	[56]
39	Yuval Rabani	[5] [56]
40	Yuri Rabinovich	[56]
41	Prabhakar Raghavan	[22]
42	Satish Rao	[22] [45] [60] [62]
43	José D. P. Rolim	[41]
44	Alexander Russell	[33]
45	Muli Safra	[47] [52]
46	Shmuel Safra	[2] [19]
47	Amit Sahai	[41]
48	Jacques Stern	[4] [12]
49	David Steurer	[61] [63] [64]
50	Madhu Sudan	[3] [13] [14] [18] [20] [37]
51	Z. Sweedyk	[4] [12]
52	Mario Szegedy	[3] [18] [20]
53	Iannis Tourlakis	[43] [50] [53]
54	Madhur Tulsiani	[61]
55	Umesh V. Vazirani	[5] [45] [60] [62]
56	Santosh Vempala	[56]
57	Nisheeth K. Vishnoi	[61]
58	Avi Wigderson	[64]
59	Andrzej Woloszyn	[23]

Colors in the list of coauthors