| 2009 |
|---|
| 62 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning.
J. ACM 56(2): (2009) |
| 2008 |
|---|
| 61 | EE | 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 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Geometry, flows, and graph-partitioning algorithms.
Commun. ACM 51(10): 96-105 (2008) |
| 2007 |
|---|
| 59 | EE | Sanjeev Arora,
Satyen Kale:
A combinatorial, primal-dual approach to semidefinite programs.
STOC 2007: 227-236 |
| 58 | EE | Sanjeev Arora,
James R. Lee,
Assaf Naor:
Fréchet Embeddings of Negative Type Metrics.
Discrete & Computational Geometry 38(4): 726-739 (2007) |
| 2006 |
|---|
| 57 | EE | Sanjeev Arora,
Elad Hazan,
Satyen Kale:
A Fast Random Sampling Algorithm for Sparsifying Matrices.
APPROX-RANDOM 2006: 272-279 |
| 56 | EE | 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 | EE | Sanjeev Arora,
Eden Chlamtac:
New approximation guarantee for chromatic number.
STOC 2006: 215-224 |
| 54 | EE | Sanjeev Arora,
George Karakostas:
A 2 + epsilon approximation algorithm for the k-MST problem.
Math. Program. 107(3): 491-504 (2006) |
| 53 | EE | 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 | EE | Sanjeev Arora,
Eli Berger,
Elad Hazan,
Guy Kindler,
Muli Safra:
On Non-Approximability for Quadratic Programs.
FOCS 2005: 206-215 |
| 51 | EE | Sanjeev Arora,
Elad Hazan,
Satyen Kale:
Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method.
FOCS 2005: 339-348 |
| 50 | EE | Michael Alekhnovich,
Sanjeev Arora,
Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.
STOC 2005: 294-303 |
| 49 | EE | Sanjeev Arora,
James R. Lee,
Assaf Naor:
Euclidean distortion and the sparsest cut.
STOC 2005: 553-562 |
| 48 | EE | Sanjeev Arora,
Bernard Chazelle:
Is the thrill gone?
Commun. ACM 48(8): 31-33 (2005) |
| 47 | EE | 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 | EE | Sanjeev Arora,
Elad Hazan,
Satyen Kale:
0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n2) Time.
FOCS 2004: 238-247 |
| 45 | EE | Sanjeev Arora,
Satish Rao,
Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning.
STOC 2004: 222-231 |
| 44 | EE | Sanjeev Arora,
Kevin L. Chang:
Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems.
Algorithmica 40(3): 189-210 (2004) |
| 43 | EE | Mikhail Alecknovich,
Sanjeev Arora,
Iannis Tourlakis:
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
Electronic Colloquium on Computational Complexity (ECCC)(117): (2004) |
| 42 | EE | 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 | EE | Sanjeev Arora:
Proving Integrality Gaps without Knowing the Linear Program.
FCT 2003: 1 |
| 39 | EE | Sanjeev Arora,
Kevin L. Chang:
Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem.
ICALP 2003: 176-188 |
| 38 | EE | Sanjeev Arora:
How NP got a new definition: a survey of probabilistically checkable proofs
CoRR cs.CC/0304038: (2003) |
| 37 | EE | Sanjeev Arora,
Madhu Sudan:
Improved Low-Degree Testing and its Applications.
Combinatorica 23(3): 365-426 (2003) |
| 36 | EE | Sanjeev Arora,
Subhash Khot:
Fitting algebraic curves to noisy data.
J. Comput. Syst. Sci. 67(2): 325-340 (2003) |
| 35 | EE | Sanjeev Arora,
George Karakostas:
Approximation Schemes for Minimum Latency Problems.
SIAM J. Comput. 32(5): 1317-1337 (2003) |
| 2002 |
|---|
| 34 | EE | Sanjeev Arora,
Béla Bollobás,
László Lovász:
Proving Integrality Gaps without Knowing the Linear Program.
FOCS 2002: 313-322 |
| 33 | EE | 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 | EE | Sanjeev Arora,
Bo Brinkman:
A randomized online algorithm for bandwidth utilization.
SODA 2002: 535-539 |
| 31 | EE | Sanjeev Arora,
Subhash Khot:
Fitting algebraic curves to noisy data.
STOC 2002: 162-169 |
| 2001 |
|---|
| 30 | EE | Sanjeev Arora:
Approximation Schemes for Geometric NP-Hard Problems: A Survey.
FSTTCS 2001: 16-17 |
| 29 | EE | Sanjeev Arora,
Ravi Kannan:
Learning mixtures of arbitrary gaussians.
STOC 2001: 247-257 |
| 2000 |
|---|
| 28 | EE | Sanjeev Arora:
Approximation algorithms that take advice.
APPROX 2000: 1 |
| 27 | EE | Sanjeev Arora,
George Karakostas:
A 2+epsilon approximation algorithm for the k-MST problem.
SODA 2000: 754-759 |
| 1999 |
|---|
| 26 | EE | Susanne Albers,
Sanjeev Arora,
Sanjeev Khanna:
Page Replacement for General Caching Problems.
SODA 1999: 31-40 |
| 25 | EE | 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 | EE | Sanjeev Arora,
Prabhakar Raghavan,
Satish Rao:
Approximation Schemes for Euclidean k-Medians and Related Problems.
STOC 1998: 106-113 |
| 21 | EE | Sanjeev Arora:
The Approximability of NP-hard Problems.
STOC 1998: 337-348 |
| 20 | EE | 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 | EE | Sanjeev Arora,
Shmuel Safra:
Probabilistic Checking of Proofs: A New Characterization of NP.
J. ACM 45(1): 70-122 (1998) |
| 18 | EE | 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 | EE | Sanjeev Arora:
Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems.
J. ACM 45(5): 753-782 (1998) |
| 1997 |
|---|
| 16 | EE | 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 | EE | Sanjeev Arora,
Madhu Sudan:
Improved Low-Degree Testing and its Applications.
STOC 1997: 485-495 |
| 13 | EE | 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 | EE | 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 | EE | Sanjeev Arora,
David R. Karger,
Marek Karpinski:
Polynomial time approximation schemes for dense instances of NP-hard problems.
STOC 1995: 284-293 |
| 1994 |
|---|
| 5 | EE | 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 |
