Sanjeev Arora

Sanjeev Arora, Rong Ge, Ali Kemal Sinop: Towards a better approximation for sparsest cut? CoRR abs/1304.3365 (2013)

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh Vempala: Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41(1): 250-271 (2012)

Sanjeev Arora, Constantinos Daskalakis, David Steurer: Message-Passing Algorithms and Improved LP Decoding. IEEE Transactions on Information Theory 58(12): 7260-7271 (2012)

Sanjeev Arora, Elad Hazan, Satyen Kale: The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8(1): 121-164 (2012)

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva: Testing Permanent Oracles - Revisited. APPROX-RANDOM 2012: 362-373

Sanjeev Arora, Rong Ge, Ankur Moitra: Learning Topic Models - Going beyond SVD. FOCS 2012: 1-10

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva: "Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders". NIPS 2012: 2384-2392

Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck: Finding overlapping communities in social networks: toward a rigorous approach. ACM Conference on Electronic Commerce 2012: 37-54

Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra: Computing a nonnegative matrix factorization - provably. STOC 2012: 145-162

Sanjeev Arora, Rong Ge, Ankur Moitra: Learning Topic Models - Going beyond SVD. CoRR abs/1204.1956 (2012)

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva: Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. CoRR abs/1206.5349 (2012)

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva: Testing Permanent Oracles -- Revisited. CoRR abs/1207.4783 (2012)

Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David Sontag, Yichen Wu, Michael Zhu: A Practical Algorithm for Topic Modeling with Provable Guarantees. CoRR abs/1212.4777 (2012)

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva: Testing Permanent Oracles - Revisited. Electronic Colloquium on Computational Complexity (ECCC) 19: 94 (2012)

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge: Computational complexity and information asymmetry in financial products. Commun. ACM 54(5): 101-107 (2011)

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. Computational Complexity 20(4): 615-648 (2011)

Sanjeev Arora, Rong Ge: New Tools for Graph Coloring. APPROX-RANDOM 2011: 1-12

Sanjeev Arora, Rong Ge: New Algorithms for Learning in Presence of Errors. ICALP (1) 2011: 403-415

Sanjeev Arora: Semidefinite Programming and Approximation Algorithms: A Survey. ISAAC 2011: 6-9

Sanjeev Arora, James R. Lee, Sushant Sachdeva: A Reformulation of the Arora-Rao-Vazirani Structure Theorem. CoRR abs/1102.1456 (2011)

Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra: Computing a Nonnegative Matrix Factorization -- Provably. CoRR abs/1111.0952 (2011)

Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck: Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach. CoRR abs/1112.1831 (2011)

Sanjeev Arora, Elad Hazan, Satyen Kale: O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n²) Time. SIAM J. Comput. 39(5): 1748-1771 (2010)

Sanjeev Arora, Boaz Barak, David Steurer: Subexponential Algorithms for Unique Games and Related Problems. FOCS 2010: 563-572

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge: Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract). ICS 2010: 49-65

Sanjeev Arora: Semidefinite Programming and Approximation Algorithms: A Survey. SWAT 2010: 25

Prahladh Harsha, 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, David Pritchard, Gwen Spencer: Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes). CoRR abs/1002.3864 (2010)

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer: Improved Algorithms for Unique Games via Divide and Conquer. Electronic Colloquium on Computational Complexity (ECCC) 17: 41 (2010)

Sanjeev Arora, Rong Ge: Learning Parities with Structured Noise. Electronic Colloquium on Computational Complexity (ECCC) 17: 66 (2010)

Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press 2009, isbn 978-0-521-42426-4, pp. I-XXIV, 1-579

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)

Sanjeev Arora, David Steurer, Avi Wigderson: Towards a Study of Low-Complexity Graphs. ICALP (1) 2009: 119-131

Sanjeev Arora, Constantinos Daskalakis, David Steurer: Message passing algorithms and improved LP decoding. STOC 2009: 3-12

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)

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

Sanjeev Arora, James R. Lee, Assaf Naor: Fréchet Embeddings of Negative Type Metrics. Discrete & Computational Geometry 38(4): 726-739 (2007)

Sanjeev Arora, Satyen Kale: A combinatorial, primal-dual approach to semidefinite programs. STOC 2007: 227-236

Sanjeev Arora, George Karakostas: A 2 + epsilon approximation algorithm for the k-MST problem. Math. Program. 107(3): 491-504 (2006)

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)

Sanjeev Arora, Elad Hazan, Satyen Kale: A Fast Random Sampling Algorithm for Sparsifying Matrices. APPROX-RANDOM 2006: 272-279

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

Sanjeev Arora, Eden Chlamtac: New approximation guarantee for chromatic number. STOC 2006: 215-224

Sanjeev Arora, Bernard Chazelle: Is the thrill gone? Commun. ACM 48(8): 31-33 (2005)

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs. FOCS 2005: 206-215

Sanjeev Arora, Elad Hazan, Satyen Kale: Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. FOCS 2005: 339-348

Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC 2005: 294-303

Sanjeev Arora, James R. Lee, Assaf Naor: Euclidean distortion and the sparsest cut. STOC 2005: 553-562

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra: On Non-Approximability for Quadratic Programs. Electronic Colloquium on Computational Complexity (ECCC)(058) (2005)

Sanjeev Arora, Kevin L. Chang: Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems. Algorithmica 40(3): 189-210 (2004)

Sanjeev Arora, Bo Brinkman: A Randomized Online Algorithm for Bandwidth Utilization. J. Scheduling 7(3): 187-194 (2004)

Sanjeev Arora, Elad Hazan, Satyen Kale: 0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n²) Time. FOCS 2004: 238-247

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231

Mikhail Alecknovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. Electronic Colloquium on Computational Complexity (ECCC)(117) (2004)

Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. Combinatorica 23(3): 365-426 (2003)

Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. J. Comput. Syst. Sci. 67(2): 325-340 (2003)

Sanjeev Arora: Approximation schemes for NP-hard geometric optimization problems: a survey. Math. Program. 97(1-2): 43-69 (2003)

Sanjeev Arora, George Karakostas: Approximation Schemes for Minimum Latency Problems. SIAM J. Comput. 32(5): 1317-1337 (2003)

Sanjeev Arora: Proving Integrality Gaps without Knowing the Linear Program. FCT 2003: 1

Sanjeev Arora, Kevin L. Chang: Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem. ICALP 2003: 176-188

Sanjeev Arora, Klaus Jansen, José D. P. Rolim, Amit Sahai (Eds.): 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, NJ, USA, August 24-26, 2003, Proceedings. Lecture Notes in Computer Science 2764, Springer 2003, isbn 3-540-40770-7

Sanjeev Arora: How NP got a new definition: a survey of probabilistically checkable proofs. CoRR cs.CC/0304038 (2003)

Sanjeev Arora, Alan M. Frieze, Haim Kaplan: A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Math. Program. 92(1): 1-36 (2002)

Sanjeev Arora, Béla Bollobás, László Lovász: Proving Integrality Gaps without Knowing the Linear Program. FOCS 2002: 313-322

Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell: A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics. NIPS 2002: 431-437

Sanjeev Arora, Bo Brinkman: A randomized online algorithm for bandwidth utilization. SODA 2002: 535-539

Sanjeev Arora, Subhash Khot: Fitting algebraic curves to noisy data. STOC 2002: 162-169

Sanjeev Arora: Approximation Schemes for Geometric NP-Hard Problems: A Survey. FSTTCS 2001: 16-17

Sanjeev Arora, Ravi Kannan: Learning mixtures of arbitrary gaussians. STOC 2001: 247-257

Sanjeev Arora: Approximation algorithms that take advice. APPROX 2000: 1

Sanjeev Arora, George Karakostas: A 2+epsilon approximation algorithm for the k-MST problem. SODA 2000: 754-759

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)

Susanne Albers, Sanjeev Arora, Sanjeev Khanna: Page Replacement for General Caching Problems. SODA 1999: 31-40

Sanjeev Arora, George Karakostas: Approximation Schemes for Minimum Latency Problems. STOC 1999: 688-693

Sanjeev Arora, Shmuel Safra: Probabilistic Checking of Proofs: A New Characterization of NP. J. ACM 45(1): 70-122 (1998)

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)

Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems. J. ACM 45(5): 753-782 (1998)

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

Sanjeev Arora, Prabhakar Raghavan, Satish Rao: Approximation Schemes for Euclidean k-Medians and Related Problems. STOC 1998: 106-113

Sanjeev Arora: The Approximability of NP-hard Problems. STOC 1998: 337-348

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)

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)

Sanjeev Arora, Ronald Fagin: On Winning Strategies in Ehrenfeucht-Fraïssé Games. Theor. Comput. Sci. 174(1-2): 97-121 (1997)

Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. FOCS 1997: 554-563

Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. RANDOM 1997: 55

Sanjeev Arora, Madhu Sudan: Improved Low-Degree Testing and its Applications. STOC 1997: 485-495

Sanjeev Arora, Madhu Sudan: Improved low-degree testing and its applications. Electronic Colloquium on Computational Complexity (ECCC) 4(3) (1997)

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)

Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. FOCS 1996: 2-11

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

Sanjeev Arora: Reductions, Codes, PCPs, and Inapproximability. FOCS 1995: 404-413

Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial time approximation schemes for dense instances of NP-hard problems. STOC 1995: 284-293

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani: Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC 1994: 459-467

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

Sanjeev Arora, Shmuel Safra: Probabilistic Checking of Proofs; A New Characterization of NP. FOCS 1992: 2-13

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy: Proof Verification and Hardness of Approximation Problems. FOCS 1992: 14-23

Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs: On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract). STOC 1990: 149-158