Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. - Aditya Bhaskara; Moses Charikar; Eden Chlamtac; Uriel Feige; Aravindan Vijayaraghavan (STOC, 2010)

Computing the Matrix p-norm - Aditya Bhaskara; Aravindan Vijayaraghavan (CoRR, 2010)

Detecting High Log-Densities – an O(n^1/4) Approximation for Densest k-Subgraph - Aditya Bhaskara; Moses Charikar; Eden Chlamtac; Uriel Feige; Aravindan Vijayaraghavan (CoRR, 2010)

Approximating Matrix p-norms. - Aditya Bhaskara; Aravindan Vijayaraghavan (SODA, 2011)

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph - Aditya Bhaskara; Moses Charikar; Venkatesan Guruswami; Aravindan Vijayaraghavan; Yuan Zhou 007 (CoRR, 2011)

Approximation Algorithms and Hardness of the k-Route Cut Problem - Julia Chuzhoy; Yury Makarychev; Aravindan Vijayaraghavan; Yuan Zhou 007 (CoRR, 2011)

On Quadratic Programming with a Ratio Objective. - Aditya Bhaskara; Moses Charikar; Rajsekar Manokaran; Aravindan Vijayaraghavan (ICALP (1), 2012)

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. - Aditya Bhaskara; Moses Charikar; Aravindan Vijayaraghavan; Venkatesan Guruswami; Yuan Zhou 007 (SODA, 2012)

Approximation algorithms for semi-random partitioning problems. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2012)

Approximation Algorithms for Semi-random Graph Partitioning Problems - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2012)

Beyond Worst Case Analysis in Approximation Algorithms - Aravindan Vijayaraghavan (2012)

Sorting noisy data with partial information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (ITCS, 2013)

Bilu-Linial Stable Instances of Max Cut - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2013)

Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? - Aditya Bhaskara; Moses Charikar; Ankur Moitra; Aravindan Vijayaraghavan (COLT, 2014)

Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. - Aditya Bhaskara; Moses Charikar; Aravindan Vijayaraghavan (COLT, 2014)

Learning Mixtures of Ranking Models. - Pranjal Awasthi; Avrim Blum; Or Sheffet; Aravindan Vijayaraghavan (NIPS, 2014)

Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (SODA, 2014)

Smoothed analysis of tensor decompositions. - Aditya Bhaskara; Moses Charikar; Ankur Moitra; Aravindan Vijayaraghavan (STOC, 2014)

Constant factor approximation for balanced cut in the PIE model. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (STOC, 2014)

Algorithms for Semi-random Correlation Clustering. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (CoRR, 2014)

Correlation Clustering with Noisy Partial Information. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2015)

Beating the random assignment on constraint satisfaction problems of bounded degree. - Boaz Barak; Ankur Moitra; Ryan O'Donnell; Prasad Raghavendra; Oded Regev 001; David Steurer; Luca Trevisan 001; Aravindan Vijayaraghavan; David Witmer; John Wright 004 (Electron. Colloquium Comput. Complex., 2015)

Learning Communities in the Presence of Errors. - Konstantin Makarychev; Yury Makarychev; Aravindan Vijayaraghavan (COLT, 2016)

Approximation Algorithms and Hardness of the k-Route Cut Problem. - Julia Chuzhoy; Yury Makarychev; Aravindan Vijayaraghavan; Yuan Zhou 007 (ACM Trans. Algorithms, 2016)

On Learning Mixtures of Well-Separated Gaussians. - Oded Regev 001; Aravindan Vijayaraghavan (FOCS, 2017)

Clustering Stable Instances of Euclidean k-means. - Aravindan Vijayaraghavan; Abhratanu Dutta; Alex Wang (NIPS, 2017)

Approximation Algorithms for Label Cover and The Log-Density Threshold. - Eden Chlamtác; Pasin Manurangsi; Dana Moshkovitz; Aravindan Vijayaraghavan (SODA, 2017)

Alpha-expansion is Exact on Stable Instances. - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (CoRR, 2017)

Optimality of Approximate Inference Algorithms on Stable Instances. - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (AISTATS, 2018)

Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. - Pranjal Awasthi; Aravindan Vijayaraghavan (FOCS, 2018)

Clustering Semi-Random Mixtures of Gaussians. - Pranjal Awasthi; Aravindan Vijayaraghavan (ICML, 2018)

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. - Arnab Bhattacharyya 001; Fabrizio Grandoni 001; Aleksandar Nikolov; Barna Saha; Saket Saurabh 001; Aravindan Vijayaraghavan; Qin Zhang 001 (ACM Trans. Algorithms, 2018)

Block Stability for MAP Inference. - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (AISTATS, 2019)

Smoothed Analysis in Unsupervised Learning via Decoupling. - Aditya Bhaskara; Aidao Chen; Aidan Perreault; Aravindan Vijayaraghavan (FOCS, 2019)

On Robustness to Adversarial Examples and Polynomial Optimization. - Pranjal Awasthi; Abhratanu Dutta; Aravindan Vijayaraghavan (NeurIPS, 2019)

Efficient Tensor Decompositions. - Aravindan Vijayaraghavan (Beyond the Worst-Case Analysis of Algorithms, 2020)

Estimating Principal Components under Adversarial Perturbations. - Pranjal Awasthi; Xue Chen 001; Aravindan Vijayaraghavan (COLT, 2020)

Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. - Biswaroop Maiti; Rajmohan Rajaraman; David Stalfa; Zoya Svitkina; Aravindan Vijayaraghavan (FOCS, 2020)

Adversarial robustness via robust low rank representations. - Pranjal Awasthi; Himanshu Jain; Ankit Singh Rawat; Aravindan Vijayaraghavan (NeurIPS, 2020)

Efficient Tensor Decomposition. - Aravindan Vijayaraghavan (CoRR, 2020)

Graph cuts always find a global optimum (with a catch). - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (CoRR, 2020)

Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances. - Hunter Lang; Aravind Reddy; David A. Sontag; Aravindan Vijayaraghavan (AISTATS, 2021)

Learning a mixture of two subspaces over finite fields. - Aidao Chen; Anindya De; Aravindan Vijayaraghavan (ALT, 2021)

Adversarially Robust Low Dimensional Representations. - Pranjal Awasthi; Vaggos Chatziafratis; Xue Chen 001; Aravindan Vijayaraghavan (COLT, 2021)

Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch). - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (ICML, 2021)

Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. - Pranjal Awasthi; Alex Tang; Aravindan Vijayaraghavan (NeurIPS, 2021)

Understanding Simultaneous Train and Test Robustness. - Pranjal Awasthi; Sivaraman Balakrishnan; Aravindan Vijayaraghavan (ALT, 2022)

Algorithms for learning a mixture of linear classifiers. - Aidao Chen; Anindya De; Aravindan Vijayaraghavan (ALT, 2022)

Classification Protocols with Minimal Disclosure. - Jinshuo Dong; Jason D. Hartline; Aravindan Vijayaraghavan (CSLAW, 2022)

Effective and Inconspicuous Over-the-Air Adversarial Examples with Adaptive Filtering. - Patrick O'Reilly; Pranjal Awasthi; Aravindan Vijayaraghavan; Bryan Pardo (ICASSP, 2022)

Training Subset Selection for Weak Supervision. - Hunter Lang; Aravindan Vijayaraghavan; David A. Sontag (NeurIPS, 2022)

The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound. - Liam O'Carroll; Vaidehi Srinivas; Aravindan Vijayaraghavan (NeurIPS, 2022)

Smoothed analysis for tensor methods in unsupervised learning. - Aditya Bhaskara; Aidao Chen; Aidan Perreault; Aravindan Vijayaraghavan (Math. Program., 2022)

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. - Nathaniel Johnston; Benjamin Lovitz; Aravindan Vijayaraghavan (FOCS, 2023)

Agnostic Learning of General ReLU Activation Using Gradient Descent. - Pranjal Awasthi; Alex Tang; Aravindan Vijayaraghavan (ICLR, 2023)

A hierarchy of eigencomputations for polynomial optimization on the sphere. - Nathaniel Johnston; Benjamin Lovitz; Aravindan Vijayaraghavan (CoRR, 2023)

Error-Tolerant E-Discovery Protocols. - Jinshuo Dong; Jason D. Hartline; Liren Shan; Aravindan Vijayaraghavan (CSLAW, 2024)

Efficient Certificates of Anti-Concentration Beyond Gaussians. - Ainesh Bakshi; Pravesh K. Kothari; Goutham Rajendran; Madhur Tulsiani; Aravindan Vijayaraghavan (FOCS, 2024)

Theoretical Analysis of Weak-to-Strong Generalization. - Hunter Lang; David A. Sontag; Aravindan Vijayaraghavan (NeurIPS, 2024)

Higher-Order Cheeger Inequality for Partitioning with Buffers. - Konstantin Makarychev; Yury Makarychev; Liren Shan; Aravindan Vijayaraghavan (SODA, 2024)

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. - Aditya Bhaskara; Eric Evert; Vaidehi Srinivas; Aravindan Vijayaraghavan (STOC, 2024)

Computing High-dimensional Confidence Sets for Arbitrary Distributions. - Chao Gao; Liren Shan; Vaidehi Srinivas; Aravindan Vijayaraghavan (COLT, 2025)

Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals. - Anxin Guo; Aravindan Vijayaraghavan (COLT, 2025)

Volume Optimality in Conformal Prediction with Structured Prediction Sets. - Chao Gao; Liren Shan; Vaidehi Srinivas; Aravindan Vijayaraghavan (CoRR, 2025)