
Sanjeev Arora
Person information
- affiliation: Princeton University, USA
- award (2012): Fulkerson Prize
- award (2011): ACM Prize in Computing
- award (2001, 2010): Gödel Prize
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2020
- [c89]Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, Sanjeev Arora:
TextHide: Tackling Data Privacy for Language Understanding Tasks. EMNLP (Findings) 2020: 1368-1382 - [c88]Sanjeev Arora:
The Quest for Mathematical Understanding of Deep Learning (Invited Talk). FSTTCS 2020: 1:1-1:1 - [c87]Zhiyuan Li, Sanjeev Arora:
An Exponential Learning Rate Schedule for Deep Learning. ICLR 2020 - [c86]Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, Dingli Yu:
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. ICLR 2020 - [c85]Sanjeev Arora, Simon S. Du, Sham M. Kakade, Yuping Luo, Nikunj Saunshi:
Provable Representation Learning for Imitation Learning via Bi-level Optimization. ICML 2020: 367-376 - [c84]Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora:
InstaHide: Instance-hiding Schemes for Private Distributed Learning. ICML 2020: 4507-4518 - [c83]Nikunj Saunshi, Yi Zhang, Mikhail Khodak, Sanjeev Arora:
A Sample Complexity Separation between Non-Convex and Convex Meta-Learning. ICML 2020: 8512-8521 - [c82]Zhiyuan Li, Kaifeng Lyu, Sanjeev Arora:
Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Rate. NeurIPS 2020 - [c81]Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, Sanjeev Arora:
Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality. NeurIPS 2020 - [i57]Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, Sanjeev Arora:
Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality. CoRR abs/2002.06668 (2020) - [i56]Sanjeev Arora, Simon S. Du, Sham M. Kakade, Yuping Luo, Nikunj Saunshi:
Provable Representation Learning for Imitation Learning via Bi-level Optimization. CoRR abs/2002.10544 (2020) - [i55]Nikunj Saunshi, Yi Zhang, Mikhail Khodak, Sanjeev Arora:
A Sample Complexity Separation between Non-Convex and Convex Meta-Learning. CoRR abs/2002.11172 (2020) - [i54]Yangsibo Huang, Yushan Su, Sachin Ravi, Zhao Song, Sanjeev Arora, Kai Li:
Privacy-preserving Learning via Deep Net Pruning. CoRR abs/2003.01876 (2020) - [i53]Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora:
InstaHide: Instance-hiding Schemes for Private Distributed Learning. CoRR abs/2010.02772 (2020) - [i52]Zhiyuan Li, Kaifeng Lyu, Sanjeev Arora:
Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Rate. CoRR abs/2010.02916 (2020) - [i51]Nikunj Saunshi, Sadhika Malladi, Sanjeev Arora:
A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks. CoRR abs/2010.03648 (2020) - [i50]Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, Sanjeev Arora:
TextHide: Tackling Data Privacy in Language Understanding Tasks. CoRR abs/2010.06053 (2020) - [i49]Zhiyuan Li, Yi Zhang, Sanjeev Arora:
Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets? CoRR abs/2010.08515 (2020)
2010 – 2019
- 2019
- [c80]Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu:
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks. ICLR (Poster) 2019 - [c79]Sanjeev Arora, Zhiyuan Li, Kaifeng Lyu:
Theoretical Analysis of Auto Rate-Tuning by Batch Normalization. ICLR (Poster) 2019 - [c78]Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang:
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019: 322-332 - [c77]Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, Hrishikesh Khandeparkar:
A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML 2019: 5628-5637 - [c76]Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo:
Implicit Regularization in Deep Matrix Factorization. NeurIPS 2019: 7411-7422 - [c75]Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang:
On Exact Computation with an Infinitely Wide Neural Net. NeurIPS 2019: 8139-8148 - [c74]Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, Sanjeev Arora:
Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets. NeurIPS 2019: 14574-14583 - [i48]Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang:
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. CoRR abs/1901.08584 (2019) - [i47]Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, Nikunj Saunshi:
A Theoretical Analysis of Contrastive Unsupervised Representation Learning. CoRR abs/1902.09229 (2019) - [i46]Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang:
On Exact Computation with an Infinitely Wide Neural Net. CoRR abs/1904.11955 (2019) - [i45]Arushi Gupta, Sanjeev Arora:
A Simple Saliency Method That Passes the Sanity Checks. CoRR abs/1905.12152 (2019) - [i44]Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo:
Implicit Regularization in Deep Matrix Factorization. CoRR abs/1905.13655 (2019) - [i43]Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Sanjeev Arora, Rong Ge:
Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets. CoRR abs/1906.06247 (2019) - [i42]Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, Dingli Yu:
Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks. CoRR abs/1910.01663 (2019) - [i41]Zhiyuan Li, Sanjeev Arora:
An Exponential Learning Rate Schedule for Deep Learning. CoRR abs/1910.07454 (2019) - [i40]Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S. Du, Wei Hu, Ruslan Salakhutdinov, Sanjeev Arora:
Enhanced Convolutional Neural Tangent Kernels. CoRR abs/1911.00809 (2019) - 2018
- [j37]Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
Learning topic models - provably and efficiently. Commun. ACM 61(4): 85-93 (2018) - [j36]Kiran Vodrahalli, Po-Hsuan Chen, Yingyu Liang, Christopher Baldassano
, Janice Chen, Esther Yong, Christopher J. Honey
, Uri Hasson, Peter J. Ramadge, Kenneth A. Norman, Sanjeev Arora:
Mapping between fMRI responses to movies and their natural language annotations. NeuroImage 180(Part): 223-231 (2018) - [j35]Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski:
Linear Algebraic Structure of Word Senses, with Applications to Polysemy. Trans. Assoc. Comput. Linguistics 6: 483-495 (2018) - [c73]Mikhail Khodak, Nikunj Saunshi, Yingyu Liang, Tengyu Ma, Brandon Stewart, Sanjeev Arora:
A La Carte Embedding: Cheap but Effective Induction of Semantic Feature Vectors. ACL (1) 2018: 12-22 - [c72]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. COLT 2018: 1455-1462 - [c71]Sanjeev Arora, Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang:
Towards Provable Control for Unknown Linear Dynamical Systems. ICLR (Workshop) 2018 - [c70]Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, Kiran Vodrahalli:
A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs. ICLR (Poster) 2018 - [c69]Sanjeev Arora, Andrej Risteski, Yi Zhang:
Do GANs learn the distribution? Some Theory and Empirics. ICLR (Poster) 2018 - [c68]Sanjeev Arora, Nadav Cohen, Elad Hazan:
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. ICML 2018: 244-253 - [c67]Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang:
Stronger Generalization Bounds for Deep Nets via a Compression Approach. ICML 2018: 254-263 - [i39]Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang:
Stronger generalization bounds for deep nets via a compression approach. CoRR abs/1802.05296 (2018) - [i38]Sanjeev Arora, Nadav Cohen, Elad Hazan:
On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization. CoRR abs/1802.06509 (2018) - [i37]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. CoRR abs/1803.01768 (2018) - [i36]Mikhail Khodak, Nikunj Saunshi, Yingyu Liang, Tengyu Ma, Brandon Stewart, Sanjeev Arora:
A La Carte Embedding: Cheap but Effective Induction of Semantic Feature Vectors. CoRR abs/1805.05388 (2018) - [i35]Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu:
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks. CoRR abs/1810.02281 (2018) - [i34]Sanjeev Arora, Zhiyuan Li, Kaifeng Lyu:
Theoretical Analysis of Auto Rate-Tuning by Batch Normalization. CoRR abs/1812.03981 (2018) - 2017
- [c66]Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, Sanjeev Arora:
On the Ability of Neural Nets to Express Distributions. COLT 2017: 1271-1296 - [c65]Sanjeev Arora, Yingyu Liang, Tengyu Ma:
A Simple but Tough-to-Beat Baseline for Sentence Embeddings. ICLR (Poster) 2017 - [c64]Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, Yi Zhang:
Generalization and Equilibrium in Generative Adversarial Nets (GANs). ICML 2017: 224-232 - [c63]Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski:
Provable learning of noisy-OR networks. STOC 2017: 1057-1066 - [i33]Holden Lee, Rong Ge, Andrej Risteski, Tengyu Ma, Sanjeev Arora:
On the ability of neural nets to express distributions. CoRR abs/1702.07028 (2017) - [i32]Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, Yi Zhang:
Generalization and Equilibrium in Generative Adversarial Nets (GANs). CoRR abs/1703.00573 (2017) - [i31]Mikhail Khodak, Andrej Risteski, Christiane Fellbaum, Sanjeev Arora:
Extending and Improving Wordnet via Unsupervised Word Embeddings. CoRR abs/1705.00217 (2017) - [i30]Sanjeev Arora, Andrej Risteski:
Provable benefits of representation learning. CoRR abs/1706.04601 (2017) - [i29]Sanjeev Arora, Yi Zhang:
Do GANs actually learn the distribution? An empirical study. CoRR abs/1706.08224 (2017) - [i28]Sanjeev Arora, Andrej Risteski, Yi Zhang:
Theoretical limitations of Encoder-Decoder GAN architectures. CoRR abs/1711.02651 (2017) - 2016
- [j34]Sanjeev Arora, Satyen Kale:
A Combinatorial, Primal-Dual Approach to Semidefinite Programs. J. ACM 63(2): 12:1-12:35 (2016) - [j33]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization - Provably. SIAM J. Comput. 45(4): 1582-1611 (2016) - [j32]Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski:
A Latent Variable Model Approach to PMI-based Word Embeddings. Trans. Assoc. Comput. Linguistics 4: 385-399 (2016) - [c62]Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra:
Provable Algorithms for Inference in Topic Models. ICML 2016: 2859-2867 - [i27]Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski:
Linear Algebraic Structure of Word Senses, with Applications to Polysemy. CoRR abs/1601.03764 (2016) - [i26]Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra:
Provable Algorithms for Inference in Topic Models. CoRR abs/1605.08491 (2016) - [i25]Kiran Vodrahalli, Po-Hsuan Chen, Yingyu Liang, Janice Chen, Esther Yong, Christopher J. Honey, Peter J. Ramadge, Kenneth A. Norman, Sanjeev Arora:
Mapping Between Natural Movie fMRI Responses and Word-Sequence Representations. CoRR abs/1610.03914 (2016) - [i24]Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski:
Provable learning of Noisy-or Networks. CoRR abs/1612.08795 (2016) - 2015
- [j31]Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva
:
Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders. Algorithmica 72(1): 215-236 (2015) - [j30]Sanjeev Arora, Vinay Kumar Nangia, Rajat Agrawal
:
Making strategy process intelligent with business intelligence: an empirical investigation. Int. J. Data Anal. Tech. Strateg. 7(1): 77-95 (2015) - [j29]Sanjeev Arora, Boaz Barak, David Steurer:
Subexponential Algorithms for Unique Games and Related Problems. J. ACM 62(5): 42:1-42:25 (2015) - [c61]Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra:
Simple, Efficient, and Neural Algorithms for Sparse Coding. COLT 2015: 113-149 - [c60]Sanjeev Arora:
Overcoming Intractability in Unsupervised Learning (Invited Talk). STACS 2015: 1-1 - [i23]Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski:
Random Walks on Context Spaces: Towards an Explanation of the Mysteries of Semantic Word Embeddings. CoRR abs/1502.03520 (2015) - [i22]Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra:
Simple, Efficient, and Neural Algorithms for Sparse Coding. CoRR abs/1503.00778 (2015) - [i21]Sanjeev Arora, Yingyu Liang, Tengyu Ma:
Why are deep nets reversible: A simple theory, with implications for training. CoRR abs/1511.05653 (2015) - 2014
- [j28]Sanjeev Arora:
Thoughts on Paper Publishing in the Digital Age. Bull. EATCS 112 (2014) - [c59]Sanjeev Arora, Rong Ge, Ankur Moitra:
New Algorithms for Learning Incoherent and Overcomplete Dictionaries. COLT 2014: 779-806 - [c58]Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma:
Provable Bounds for Learning Some Deep Representations. ICML 2014: 584-592 - [c57]Prabhat Chand
, Pratima Murthy, Vivek Gupta, Arun Kandasamy, Deepak Jayarajan, Lakshmanan Sethu
, Vivek Benegal
, Mathew Varghese
, Miriam Komaromy, Sanjeev Arora:
Technology Enhanced Learning in Addiction Mental Health: Developing a Virtual Knowledge Network: NIMHANS ECHO. T4E 2014: 229-232 - [i20]Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma:
More Algorithms for Provable Dictionary Learning. CoRR abs/1401.0579 (2014) - 2013
- [c56]Sanjeev Arora, Rong Ge, Ali Kemal Sinop:
Towards a Better Approximation for Sparsest Cut? FOCS 2013: 270-279 - [c55]Sanjeev Arora, Rong Ge, Yonatan Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
A Practical Algorithm for Topic Modeling with Provable Guarantees. ICML (2) 2013: 280-288 - [i19]Sanjeev Arora, Rong Ge, Ali Kemal Sinop:
Towards a better approximation for sparsest cut? CoRR abs/1304.3365 (2013) - [i18]Sanjeev Arora, Rong Ge, Ankur Moitra:
New Algorithms for Learning Incoherent and Overcomplete Dictionaries. CoRR abs/1308.6273 (2013) - [i17]Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma:
Provable Bounds for Learning Some Deep Representations. CoRR abs/1310.6343 (2013) - 2012
- [j27]Sanjeev Arora:
The Gödel Price 2013. Call for Nominations. Bull. EATCS 108: 17-21 (2012) - [j26]Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala:
Local Versus Global Properties of Metric Spaces. SIAM J. Comput. 41(1): 250-271 (2012) - [j25]Sanjeev Arora, Constantinos Daskalakis, David Steurer:
Message-Passing Algorithms and Improved LP Decoding. IEEE Trans. Inf. Theory 58(12): 7260-7271 (2012) - [j24]Sanjeev Arora, Elad Hazan, Satyen Kale:
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory Comput. 8(1): 121-164 (2012) - [c54]Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva
:
Testing Permanent Oracles - Revisited. APPROX-RANDOM 2012: 362-373 - [c53]Sanjeev Arora, Rong Ge, Ankur Moitra:
Learning Topic Models - Going beyond SVD. FOCS 2012: 1-10 - [c52]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 - [c51]Sanjeev Arora, Eunjee Song, Yoonjeong Kim:
Modified hierarchical privacy-aware role based access control model. RACS 2012: 344-347 - [c50]Sanjeev Arora, Rong Ge, Sushant Sachdeva
, Grant Schoenebeck:
Finding overlapping communities in social networks: toward a rigorous approach. EC 2012: 37-54 - [c49]Sanjeev Arora, Rong Ge, Ravindran Kannan, Ankur Moitra:
Computing a nonnegative matrix factorization - provably. STOC 2012: 145-162 - [i16]Sanjeev Arora, Rong Ge, Ankur Moitra:
Learning Topic Models - Going beyond SVD. CoRR abs/1204.1956 (2012) - [i15]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) - [i14]Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles -- Revisited. CoRR abs/1207.4783 (2012) - [i13]Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu:
A Practical Algorithm for Topic Modeling with Provable Guarantees. CoRR abs/1212.4777 (2012) - [i12]Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. Electron. Colloquium Comput. Complex. 19: 94 (2012) - 2011
- [j23]Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge:
Computational complexity and information asymmetry in financial products. Commun. ACM 54(5): 101-107 (2011) - [j22]Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis:
Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. Comput. Complex. 20(4): 615-648 (2011) - [c48]Sanjeev Arora, Rong Ge:
New Tools for Graph Coloring. APPROX-RANDOM 2011: 1-12 - [c47]Masoud Naghedolfeizi, Sanjeev Arora, James E. Glover:
Visualizing conductive and convective heat transfer using thermographic techniques. FIE 2011: 3 - [c46]Sanjeev Arora, Rong Ge:
New Algorithms for Learning in Presence of Errors. ICALP (1) 2011: 403-415 - [c45]Sanjeev Arora:
Semidefinite Programming and Approximation Algorithms: A Survey. ISAAC 2011: 6-9 - [i11]Sanjeev Arora, James R. Lee, Sushant Sachdeva:
A Reformulation of the Arora-Rao-Vazirani Structure Theorem. CoRR abs/1102.1456 (2011) - [i10]Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra:
Computing a Nonnegative Matrix Factorization -- Provably. CoRR abs/1111.0952 (2011) - [i9]Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck:
Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach. CoRR abs/1112.1831 (2011) - 2010
- [j21]Sanjeev Arora, Elad Hazan
, Satyen Kale:
O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n2) Time. SIAM J. Comput. 39(5): 1748-1771 (2010) - [c44]Sanjeev Arora, Boaz Barak, David Steurer:
Subexponential Algorithms for Unique Games and Related Problems. FOCS 2010: 563-572 - [c43]Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge:
Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract). ICS 2010: 49-65 - [c42]Sanjeev Arora:
Semidefinite Programming and Approximation Algorithms: A Survey. SWAT 2010: 25 - [i8]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) - [i7]Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer:
Improved Algorithms for Unique Games via Divide and Conquer. Electron. Colloquium Comput. Complex. 17: 41 (2010) - [i6]Sanjeev Arora, Rong Ge:
Learning Parities with Structured Noise. Electron. Colloquium Comput. Complex. 17: 66 (2010)
2000 – 2009
- 2009
- [b1]Sanjeev Arora, Boaz Barak:
Computational Complexity - A Modern Approach. Cambridge University Press 2009, ISBN 978-0-521-42426-4, pp. I-XXIV, 1-579 - [j20]Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): 5:1-5:37 (2009) - [c41]Sanjeev Arora, David Steurer, Avi Wigderson:
Towards a Study of Low-Complexity Graphs. ICALP (1) 2009: 119-131 - [c40]Sanjeev Arora, Constantinos Daskalakis, David Steurer:
Message passing algorithms and improved LP decoding. STOC 2009: 3-12 - 2008
- [j19]Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008) - [c39]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 - 2007
- [j18]Sanjeev Arora, James R. Lee, Assaf Naor:
Fréchet Embeddings of Negative Type Metrics. Discret. Comput. Geom. 38(4): 726-739 (2007) - [c38]Sanjeev Arora, Satyen Kale:
A combinatorial, primal-dual approach to semidefinite programs. STOC 2007: 227-236 - 2006
- [j17]Sanjeev Arora, George Karakostas
:
A 2 + epsilon approximation algorithm for the k-MST problem. Math. Program. 107(3): 491-504 (2006) - [j16]Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis:
Proving Integrality Gaps without Knowing the Linear Program. Theory Comput. 2(2): 19-51 (2006) - [c37]