Sanjeev Arora

According to our database, Sanjeev Arora authored at least 158 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Keeping LLMs Aligned After Fine-tuning: The Crucial Role of Prompt Templates.

Kaifeng Lyu, Haoyu Zhao, Xinran Gu, Dingli Yu, Anirudh Goyal, Sanjeev Arora

CoRR, 2024

Language Models as Science Tutors.

Alexis Chevalier, Jiayi Geng, Alexander Wettig, Howard Chen, Sebastian Mizera, Toni Annala, Max Jameson Aragon, Arturo Rodríguez Fanlo, Simon Frieder, Simon Machado, Akshara Prabhakar, Ellie Thieu, Jiachen T. Wang, Zirui Wang, Xindi Wu, Mengzhou Xia, Wenhan Jia, Jiatong Yu, Jun-Jie Zhu, Zhiyong Jason Ren, Sanjeev Arora, Danqi Chen

CoRR, 2024

LESS: Selecting Influential Data for Targeted Instruction Tuning.

Mengzhou Xia, Sadhika Malladi, Suchin Gururangan, Sanjeev Arora, Danqi Chen

CoRR, 2024

2023

Unlearning via Sparse Representations.

Vedant Shah, Frederik Träuble, Ashish Malik, Hugo Larochelle, Michael Mozer, Sanjeev Arora, Yoshua Bengio, Anirudh Goyal

CoRR, 2023

Skill-Mix: a Flexible and Expandable Family of Evaluations for AI models.

Dingli Yu, Simran Kaur, Arushi Gupta, Jonah Brown-Cohen, Anirudh Goyal, Sanjeev Arora

CoRR, 2023

A Quadratic Synchronization Rule for Distributed Deep Learning.

Xinran Gu, Kaifeng Lyu, Sanjeev Arora, Jingzhao Zhang, Longbo Huang

CoRR, 2023

A Theory for Emergence of Complex Skills in Language Models.

Sanjeev Arora, Anirudh Goyal

CoRR, 2023

Trainable Transformer in Transformer.

Abhishek Panigrahi, Sadhika Malladi, Mengzhou Xia, Sanjeev Arora

CoRR, 2023

Fine-Tuning Language Models with Just Forward Passes.

Sadhika Malladi, Tianyu Gao, Eshaan Nichani, Alex Damian, Jason D. Lee, Danqi Chen, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Task-Specific Skill Localization in Fine-tuned Language Models.

Abhishek Panigrahi, Nikunj Saunshi, Haoyu Zhao, Sanjeev Arora

Proceedings of the International Conference on Machine Learning, 2023

A Kernel-Based View of Language Model Fine-Tuning.

Sadhika Malladi, Alexander Wettig, Dingli Yu, Danqi Chen, Sanjeev Arora

Proceedings of the International Conference on Machine Learning, 2023

Understanding Influence Functions and Datamodels via Harmonic Analysis.

Nikunj Saunshi, Arushi Gupta, Mark Braverman, Sanjeev Arora

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Why (and When) does Local SGD Generalize Better than SGD?

Xinran Gu, Kaifeng Lyu, Longbo Huang, Sanjeev Arora

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Do Transformers Parse while Predicting the Masked Word?

Haoyu Zhao, Abhishek Panigrahi, Rong Ge, Sanjeev Arora

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

2022

Adaptive Gradient Methods with Local Guarantees.

Zhou Lu, Wenhan Xia, Sanjeev Arora, Elad Hazan

CoRR, 2022

On the SDEs and Scaling Rules for Adaptive Gradient Algorithms.

Sadhika Malladi, Kaifeng Lyu, Abhishek Panigrahi, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction.

Kaifeng Lyu, Zhiyuan Li, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

New Definitions and Evaluations for Saliency Methods: Staying Intrinsic, Complete and Sound.

Arushi Gupta, Nikunj Saunshi, Dingli Yu, Kaifeng Lyu, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Implicit Bias of Gradient Descent on Reparametrized Models: On Equivalence to Mirror Descent.

Zhiyuan Li, Tianhao Wang, Jason D. Lee, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Understanding Contrastive Learning Requires Incorporating Inductive Biases.

Nikunj Saunshi, Jordan T. Ash, Surbhi Goel, Dipendra Misra, Cyril Zhang, Sanjeev Arora, Sham M. Kakade, Akshay Krishnamurthy

Proceedings of the International Conference on Machine Learning, 2022

Understanding Gradient Descent on the Edge of Stability in Deep Learning.

Sanjeev Arora, Zhiyuan Li, Abhishek Panigrahi

Proceedings of the International Conference on Machine Learning, 2022

On Predicting Generalization using GANs.

Yi Zhang, Arushi Gupta, Nikunj Saunshi, Sanjeev Arora

Proceedings of the Tenth International Conference on Learning Representations, 2022

What Happens after SGD Reaches Zero Loss? --A Mathematical Framework.

Zhiyuan Li, Tianhao Wang, Sanjeev Arora

Proceedings of the Tenth International Conference on Learning Representations, 2022

2021

Rip van Winkle's Razor: A Simple Estimate of Overfit to Test Data.

Sanjeev Arora, Yi Zhang

CoRR, 2021

Technical perspective: Why don't today's deep nets overfit to their training data?

Sanjeev Arora

Commun. ACM, 2021

Opening the Black Box of Deep Learning: Some Lessons and Take-aways.

Sanjeev Arora

Proceedings of the SIGMETRICS '21: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 2021

Gradient Descent on Two-layer Nets: Margin Maximization and Simplicity Bias.

Kaifeng Lyu, Zhiyuan Li, Runzhe Wang, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On the Validity of Modeling SGD with Stochastic Differential Equations (SDEs).

Zhiyuan Li, Sadhika Malladi, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Evaluating Gradient Inversion Attacks and Defenses in Federated Learning.

Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

A Mathematical Exploration of Why Language Models Help Solve Downstream Tasks.

Nikunj Saunshi, Sadhika Malladi, Sanjeev Arora

Proceedings of the 9th International Conference on Learning Representations, 2021

Why Are Convolutional Nets More Sample-Efficient than Fully-Connected Nets?

Zhiyuan Li, Yi Zhang, Sanjeev Arora

Proceedings of the 9th International Conference on Learning Representations, 2021

2020

Privacy-preserving Learning via Deep Net Pruning.

Yangsibo Huang, Yushan Su, Sachin Ravi, Zhao Song, Sanjeev Arora, Kai Li

CoRR, 2020

Over-parameterized Adversarial Training: An Analysis Overcoming the Curse of Dimensionality.

Yi Zhang, Orestis Plevrakis, Simon S. Du, Xingguo Li, Zhao Song, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Reconciling Modern Deep Learning with Traditional Optimization Analyses: The Intrinsic Learning Rate.

Zhiyuan Li, Kaifeng Lyu, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

A Sample Complexity Separation between Non-Convex and Convex Meta-Learning.

Nikunj Saunshi, Yi Zhang, Mikhail Khodak, Sanjeev Arora

Proceedings of the 37th International Conference on Machine Learning, 2020

InstaHide: Instance-hiding Schemes for Private Distributed Learning.

Yangsibo Huang, Zhao Song, Kai Li, Sanjeev Arora

Proceedings of the 37th International Conference on Machine Learning, 2020

Provable Representation Learning for Imitation Learning via Bi-level Optimization.

Sanjeev Arora, Simon S. Du, Sham M. Kakade, Yuping Luo, Nikunj Saunshi

Proceedings of the 37th International Conference on Machine Learning, 2020

Harnessing the Power of Infinitely Wide Deep Nets on Small-data Tasks.

Sanjeev Arora, Simon S. Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, Dingli Yu

Proceedings of the 8th International Conference on Learning Representations, 2020

An Exponential Learning Rate Schedule for Deep Learning.

Zhiyuan Li, Sanjeev Arora

Proceedings of the 8th International Conference on Learning Representations, 2020

The Quest for Mathematical Understanding of Deep Learning (Invited Talk).

Sanjeev Arora

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

TextHide: Tackling Data Privacy for Language Understanding Tasks.

Yangsibo Huang, Zhao Song, Danqi Chen, Kai Li, Sanjeev Arora

Proceedings of the Findings of the Association for Computational Linguistics: EMNLP 2020, 2020

2019

Enhanced Convolutional Neural Tangent Kernels.

Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S. Du, Wei Hu, Ruslan Salakhutdinov, Sanjeev Arora

CoRR, 2019

A Simple Saliency Method That Passes the Sanity Checks.

Arushi Gupta, Sanjeev Arora

CoRR, 2019

Explaining Landscape Connectivity of Low-cost Solutions for Multilayer Nets.

Rohith Kuditipudi, Xiang Wang, Holden Lee, Yi Zhang, Zhiyuan Li, Wei Hu, Rong Ge, Sanjeev Arora

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

On Exact Computation with an Infinitely Wide Neural Net.

Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Implicit Regularization in Deep Matrix Factorization.

Sanjeev Arora, Nadav Cohen, Wei Hu, Yuping Luo

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Theoretical Analysis of Contrastive Unsupervised Representation Learning.

Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, Hrishikesh Khandeparkar

Proceedings of the 36th International Conference on Machine Learning, 2019

Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks.

Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang

Proceedings of the 36th International Conference on Machine Learning, 2019

Theoretical Analysis of Auto Rate-Tuning by Batch Normalization.

Sanjeev Arora, Zhiyuan Li, Kaifeng Lyu

Proceedings of the 7th International Conference on Learning Representations, 2019

A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks.

Sanjeev Arora, Nadav Cohen, Noah Golowich, Wei Hu

Proceedings of the 7th International Conference on Learning Representations, 2019

2018

Linear Algebraic Structure of Word Senses, with Applications to Polysemy.

Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski

Trans. Assoc. Comput. Linguistics, 2018

Mapping between fMRI responses to movies and their natural language annotations.

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

NeuroImage, 2018

Learning topic models - provably and efficiently.

Sanjeev Arora, Rong Ge, Yoni Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu

Commun. ACM, 2018

On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization.

Sanjeev Arora, Nadav Cohen, Elad Hazan

Proceedings of the 35th International Conference on Machine Learning, 2018

Stronger Generalization Bounds for Deep Nets via a Compression Approach.

Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang

Proceedings of the 35th International Conference on Machine Learning, 2018

Do GANs learn the distribution? Some Theory and Empirics.

Sanjeev Arora, Andrej Risteski, Yi Zhang

Proceedings of the 6th International Conference on Learning Representations, 2018

A Compressed Sensing View of Unsupervised Text Embeddings, Bag-of-n-Grams, and LSTMs.

Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, Kiran Vodrahalli

Proceedings of the 6th International Conference on Learning Representations, 2018

Towards Provable Control for Unknown Linear Dynamical Systems.

Sanjeev Arora, Elad Hazan, Holden Lee, Karan Singh, Cyril Zhang, Yi Zhang

Proceedings of the 6th International Conference on Learning Representations, 2018

An Analysis of the t-SNE Algorithm for Data Visualization.

Sanjeev Arora, Wei Hu, Pravesh K. Kothari

Proceedings of the Conference On Learning Theory, 2018

A La Carte Embedding: Cheap but Effective Induction of Semantic Feature Vectors.

Mikhail Khodak, Nikunj Saunshi, Yingyu Liang, Tengyu Ma, Brandon Stewart, Sanjeev Arora

Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, 2018

2017

Theoretical limitations of Encoder-Decoder GAN architectures.

Sanjeev Arora, Andrej Risteski, Yi Zhang

CoRR, 2017

Extending and Improving Wordnet via Unsupervised Word Embeddings.

Mikhail Khodak, Andrej Risteski, Christiane Fellbaum, Sanjeev Arora

CoRR, 2017

Do GANs actually learn the distribution? An empirical study.

Sanjeev Arora, Yi Zhang

CoRR, 2017

Provable benefits of representation learning.

Sanjeev Arora, Andrej Risteski

CoRR, 2017

Provable learning of noisy-OR networks.

Sanjeev Arora, Rong Ge, Tengyu Ma, Andrej Risteski

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Generalization and Equilibrium in Generative Adversarial Nets (GANs).

Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, Yi Zhang

Proceedings of the 34th International Conference on Machine Learning, 2017

A Simple but Tough-to-Beat Baseline for Sentence Embeddings.

Sanjeev Arora, Yingyu Liang, Tengyu Ma

Proceedings of the 5th International Conference on Learning Representations, 2017

On the Ability of Neural Nets to Express Distributions.

Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, Sanjeev Arora

Proceedings of the 30th Conference on Learning Theory, 2017

2016

A Latent Variable Model Approach to PMI-based Word Embeddings.

Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski

Trans. Assoc. Comput. Linguistics, 2016

Computing a Nonnegative Matrix Factorization - Provably.

Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

SIAM J. Comput., 2016

A Combinatorial, Primal-Dual Approach to Semidefinite Programs.

Sanjeev Arora, Satyen Kale

J. ACM, 2016

Mapping Between Natural Movie fMRI Responses and Word-Sequence Representations.

Kiran Vodrahalli, Po-Hsuan Chen, Yingyu Liang, Janice Chen, Esther Yong, Christopher J. Honey, Peter J. Ramadge, Kenneth A. Norman, Sanjeev Arora

CoRR, 2016

Provable Algorithms for Inference in Topic Models.

Sanjeev Arora, Rong Ge, Frederic Koehler, Tengyu Ma, Ankur Moitra

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Subexponential Algorithms for Unique Games and Related Problems.

Sanjeev Arora, Boaz Barak, David Steurer

J. ACM, 2015

Making strategy process intelligent with business intelligence: an empirical investigation.

Sanjeev Arora, Vinay Kumar Nangia, Rajat Agrawal

Int. J. Data Anal. Tech. Strateg., 2015

Why are deep nets reversible: A simple theory, with implications for training.

Sanjeev Arora, Yingyu Liang, Tengyu Ma

CoRR, 2015

Random Walks on Context Spaces: Towards an Explanation of the Mysteries of Semantic Word Embeddings.

Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, Andrej Risteski

CoRR, 2015

Provable ICA with Unknown Gaussian Noise, and Implications for Gaussian Mixtures and Autoencoders.

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Algorithmica, 2015

Overcoming Intractability in Unsupervised Learning (Invited Talk).

Sanjeev Arora

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Simple, Efficient, and Neural Algorithms for Sparse Coding.

Sanjeev Arora, Rong Ge, Tengyu Ma, Ankur Moitra

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Thoughts on Paper Publishing in the Digital Age.

Sanjeev Arora

Bull. EATCS, 2014

More Algorithms for Provable Dictionary Learning.

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

CoRR, 2014

Technology Enhanced Learning in Addiction Mental Health: Developing a Virtual Knowledge Network: NIMHANS ECHO.

Prabhat Chand, Pratima Murthy, Vivek Gupta, Arun Kandasamy, Deepak Jayarajan, Lakshmanan Sethu, Vivek Benegal, Mathew Varghese, Miriam Komaromy, Sanjeev Arora

Proceedings of the Sixth IEEE International Conference on Technology for Education, 2014

Provable Bounds for Learning Some Deep Representations.

Sanjeev Arora, Aditya Bhaskara, Rong Ge, Tengyu Ma

Proceedings of the 31th International Conference on Machine Learning, 2014

New Algorithms for Learning Incoherent and Overcomplete Dictionaries.

Sanjeev Arora, Rong Ge, Ankur Moitra

Proceedings of The 27th Conference on Learning Theory, 2014

2013

A Practical Algorithm for Topic Modeling with Provable Guarantees.

Sanjeev Arora, Rong Ge, Yonatan Halpern, David M. Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu

Proceedings of the 30th International Conference on Machine Learning, 2013

Towards a Better Approximation for Sparsest Cut?

Sanjeev Arora, Rong Ge, Ali Kemal Sinop

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

The Multiplicative Weights Update Method: a Meta-Algorithm and Applications.

Sanjeev Arora, Elad Hazan, Satyen Kale

Theory Comput., 2012

Message-Passing Algorithms and Improved LP Decoding.

Sanjeev Arora, Constantinos Daskalakis, David Steurer

IEEE Trans. Inf. Theory, 2012

Local Versus Global Properties of Metric Spaces.

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala

SIAM J. Comput., 2012

Testing Permanent Oracles - Revisited.

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2012

The Gödel Price 2013. Call for Nominations.

Sanjeev Arora

Bull. EATCS, 2012

Finding overlapping communities in social networks: toward a rigorous approach.

Sanjeev Arora, Rong Ge, Sushant Sachdeva, Grant Schoenebeck

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

<i>Modified</i> hierarchical privacy-aware role based access control model.

Sanjeev Arora, Eunjee Song, Yoonjeong Kim

Proceedings of the Research in Applied Computation Symposium, 2012

"Provable ICA with Unknown Gaussian Noise, with Implications for Gaussian Mixtures and Autoencoders".

Sanjeev Arora, Rong Ge, Ankur Moitra, Sushant Sachdeva

Proceedings of the Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012

Learning Topic Models - Going beyond SVD.

Sanjeev Arora, Rong Ge, Ankur Moitra

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

A Reformulation of the Arora-Rao-Vazirani Structure Theorem

Sanjeev Arora, James R. Lee, Sushant Sachdeva

CoRR, 2011

Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy.

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Comput. Complex., 2011

Computational complexity and information asymmetry in financial products.

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Commun. ACM, 2011

Semidefinite Programming and Approximation Algorithms: A Survey.

Sanjeev Arora

Proceedings of the Algorithms and Computation - 22nd International Symposium, 2011

New Algorithms for Learning in Presence of Errors.

Sanjeev Arora, Rong Ge

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Visualizing conductive and convective heat transfer using thermographic techniques.

Masoud Naghedolfeizi, Sanjeev Arora, James E. Glover

Proceedings of the 2011 Frontiers in Education Conference, 2011

New Tools for Graph Coloring.

Sanjeev Arora, Rong Ge

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

O(sqrt(log(n)) Approximation to SPARSEST CUT in Õ(n²) Time.

Sanjeev Arora, Elad Hazan, Satyen Kale

SIAM J. Comput., 2010

Improved Algorithms for Unique Games via Divide and Conquer.

Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer

Electron. Colloquium Comput. Complex., 2010

Learning Parities with Structured Noise.

Sanjeev Arora, Rong Ge

Electron. Colloquium Comput. Complex., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

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

CoRR, 2010

Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract).

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Proceedings of the Innovations in Computer Science, 2010

2009

Expander flows, geometric embeddings and graph partitioning.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

J. ACM, 2009

Towards a Study of Low-Complexity Graphs.

Sanjeev Arora, David Steurer, Avi Wigderson

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Computational Complexity - A Modern Approach.

Sanjeev Arora, Boaz Barak

Cambridge University Press, ISBN: 978-0-521-42426-4, 2009

2008

Geometry, flows, and graph-partitioning algorithms.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

Commun. ACM, 2008

Unique games on expanding constraint graphs are easy: extended abstract.

Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, Nisheeth K. Vishnoi

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Fréchet Embeddings of Negative Type Metrics.

Sanjeev Arora, James R. Lee, Assaf Naor

Discret. Comput. Geom., 2007

2006

Proving Integrality Gaps without Knowing the Linear Program.

Sanjeev Arora, Béla Bollobás, László Lovász, Iannis Tourlakis

Theory Comput., 2006

A 2 + <i>epsilon</i> approximation algorithm for the <i>k</i>-MST problem.

Sanjeev Arora, George Karakostas

Math. Program., 2006

New approximation guarantee for chromatic number.

Sanjeev Arora, Eden Chlamtac

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

A Fast Random Sampling Algorithm for Sparsifying Matrices.

Sanjeev Arora, Elad Hazan, Satyen Kale

Proceedings of the Approximation, 2006

2005

On Non-Approximability for Quadratic Programs

Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra

Electron. Colloquium Comput. Complex., 2005

Is the thrill gone?

Sanjeev Arora, Bernard Chazelle

Commun. ACM, 2005

Euclidean distortion and the sparsest cut.

Sanjeev Arora, James R. Lee, Assaf Naor

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method.

Sanjeev Arora, Elad Hazan, Satyen Kale

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

A Randomized Online Algorithm for Bandwidth Utilization.

Sanjeev Arora, Bo Brinkman

J. Sched., 2004

Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problems.

Sanjeev Arora, Kevin L. Chang

Algorithmica, 2004

0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n²) Time.

Sanjeev Arora, Elad Hazan, Satyen Kale

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Exploring complexity through reductions.

Sanjeev Arora

Proceedings of the Computational Complexity Theory., 2004

2003

Approximation Schemes for Minimum Latency Problems.

Sanjeev Arora, George Karakostas

SIAM J. Comput., 2003

Approximation schemes for NP-hard geometric optimization problems: a survey.

Sanjeev Arora

Math. Program., 2003

Fitting algebraic curves to noisy data.

Sanjeev Arora, Subhash Khot

J. Comput. Syst. Sci., 2003

How NP got a new definition: a survey of probabilistically checkable proofs

Sanjeev Arora

CoRR, 2003

Improved Low-Degree Testing and its Applications.

Sanjeev Arora, Madhu Sudan

Comb., 2003

Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem.

Sanjeev Arora, Kevin L. Chang

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

Proving Integrality Gaps without Knowing the Linear Program.

Sanjeev Arora

Proceedings of the Fundamentals of Computation Theory, 14th International Symposium, 2003

2002

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems.

Sanjeev Arora, Alan M. Frieze, Haim Kaplan

Math. Program., 2002

A Note on the Representational Incompatibility of Function Approximation and Factored Dynamics.

Eric Allender, Sanjeev Arora, Michael J. Kearns, Cristopher Moore, Alexander Russell

Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002

Proving Integrality Gaps without Knowing the Linear Program.

Sanjeev Arora, Béla Bollobás, László Lovász

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Learning mixtures of arbitrary gaussians.

Sanjeev Arora, Ravi Kannan

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Approximation Schemes for Geometric NP-Hard Problems: A Survey.

Sanjeev Arora

Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

2000

A 2+epsilon approximation algorithm for the <i>k</i>-MST problem.

Sanjeev Arora, George Karakostas

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Approximation algorithms that take advice.

Sanjeev Arora

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems.

Sanjeev Arora, David R. Karger, Marek Karpinski

J. Comput. Syst. Sci., 1999

Page Replacement for General Caching Problems.

Susanne Albers, Sanjeev Arora, Sanjeev Khanna

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

Probabilistic Checking of Proofs: A New Characterization of NP.

Sanjeev Arora, Shmuel Safra

J. ACM, 1998

Proof Verification and the Hardness of Approximation Problems.

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

J. ACM, 1998

Polynomial Time Approximation Schemes for Euclidean Traveling Salesman and other Geometric Problems.

Sanjeev Arora

J. ACM, 1998

Approximation Schemes for Euclidean <i>k</i>-Medians and Related Problems.

Sanjeev Arora, Prabhakar Raghavan, Satish Rao

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Approximability of NP-hard Problems.

Sanjeev Arora

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.

Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

1997

On Winning Strategies in Ehrenfeucht-Fraïssé Games.

Sanjeev Arora, Ronald Fagin

Theor. Comput. Sci., 1997

The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations.

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

J. Comput. Syst. Sci., 1997

Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems.

Sanjeev Arora

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996

On-Line Algorithms for Path Selection in a Nonblocking Network.

Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs

SIAM J. Comput., 1996

Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems.

Sanjeev Arora

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Polynomial time approximation schemes for dense instances of <i>NP</i>-hard problems.

Sanjeev Arora, David R. Karger, Marek Karpinski

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Reductions, Codes, PCPs, and Inapproximability.

Sanjeev Arora

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Simulating quadratic dynamical systems is PSPACE-complete (preliminary version).

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations

Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1990

On-line Algorithms for Path Selection in a Nonblocking Network (Extended Abstract)

Sanjeev Arora, Frank Thomson Leighton, Bruce M. Maggs

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990