Aravindan Vijayaraghavan

103 papers A* 35A 4B 3Misc 1Journal 52Unranked 6

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Compact Conformal Subgraphs. CoRR Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, Aravindan Vijayaraghavan
2026	J	`jnl`	Low-Degree Method Fails to Predict Robust Subspace Recovery. CoRR He Jia, Aravindan Vijayaraghavan
2025	A*	`conf`	Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals. COLT Anxin Guo, Aravindan Vijayaraghavan
2025	A*	`conf`	Computing High-dimensional Confidence Sets for Arbitrary Distributions. COLT Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
2025	J	`jnl`	Computing High-dimensional Confidence Sets for Arbitrary Distributions. CoRR Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
2025	J	`jnl`	Learning Confidence Ellipsoids and Applications to Robust Subspace Recovery. CoRR Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
2025	A*	`conf`	Volume Optimality in Conformal Prediction with Structured Prediction Sets. ICML Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
2025	J	`jnl`	Volume Optimality in Conformal Prediction with Structured Prediction Sets. CoRR Chao Gao, Liren Shan, Vaidehi Srinivas, Aravindan Vijayaraghavan
2024	J	`jnl`	Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals. CoRR Anxin Guo, Aravindan Vijayaraghavan
2024	A*	`conf`	Efficient Certificates of Anti-Concentration Beyond Gaussians. FOCS Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
2024	J	`jnl`	Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
2024	—	`conf`	Error-Tolerant E-Discovery Protocols. CSLAW Jinshuo Dong, Jason D. Hartline, Liren Shan, Aravindan Vijayaraghavan
2024	J	`jnl`	Error-Tolerant E-Discovery Protocols. CoRR Jinshuo Dong, Jason D. Hartline, Liren Shan, Aravindan Vijayaraghavan
2024	A*	`conf`	Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2024	A*	`conf`	New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. STOC Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan
2024	J	`jnl`	New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. CoRR Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan
2024	A*	`conf`	Theoretical Analysis of Weak-to-Strong Generalization. NeurIPS Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2024	J	`jnl`	Theoretical Analysis of Weak-to-Strong Generalization. CoRR Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2023	J	`jnl`	A hierarchy of eigencomputations for polynomial optimization on the sphere. CoRR Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
2023	A*	`conf`	Agnostic Learning of General ReLU Activation Using Gradient Descent. ICLR Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
2023	A*	`conf`	Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. FOCS Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
2023	J	`jnl`	Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan
2022	J	`jnl`	Agnostic Learning of General ReLU Activation Using Gradient Descent. CoRR Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
2022	B	`conf`	Algorithms for learning a mixture of linear classifiers. ALT Aidao Chen, Anindya De, Aravindan Vijayaraghavan
2022	—	`conf`	Classification Protocols with Minimal Disclosure. CSLAW Jinshuo Dong, Jason D. Hartline, Aravindan Vijayaraghavan
2022	J	`jnl`	Classification Protocols with Minimal Disclosure. CoRR Jinshuo Dong, Jason D. Hartline, Aravindan Vijayaraghavan
2022	J	`jnl`	Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. CoRR Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan
2022	Misc	`conf`	Effective and Inconspicuous Over-the-Air Adversarial Examples with Adaptive Filtering. ICASSP Patrick O'Reilly, Pranjal Awasthi, Aravindan Vijayaraghavan, Bryan Pardo
2022	J	`jnl`	Smoothed analysis for tensor methods in unsupervised learning. Math. Program. Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan
2022	A*	`conf`	The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound. NeurIPS Liam O'Carroll, Vaidehi Srinivas, Aravindan Vijayaraghavan
2022	J	`jnl`	The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound. CoRR Liam O'Carroll, Vaidehi Srinivas, Aravindan Vijayaraghavan
2022	A*	`conf`	Training Subset Selection for Weak Supervision. NeurIPS Hunter Lang, Aravindan Vijayaraghavan, David A. Sontag
2022	J	`jnl`	Training Subset Selection for Weak Supervision. CoRR Hunter Lang, Aravindan Vijayaraghavan, David A. Sontag
2022	B	`conf`	Understanding Simultaneous Train and Test Robustness. ALT Pranjal Awasthi, Sivaraman Balakrishnan, Aravindan Vijayaraghavan
2021	A*	`conf`	Adversarially Robust Low Dimensional Representations. COLT Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan
2021	A	`conf`	Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances. AISTATS Hunter Lang, Aravind Reddy, David A. Sontag, Aravindan Vijayaraghavan
2021	J	`jnl`	Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances. CoRR Hunter Lang, Aravind Reddy, David A. Sontag, Aravindan Vijayaraghavan
2021	A*	`conf`	Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. NeurIPS Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
2021	J	`jnl`	Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. CoRR Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan
2021	A*	`conf`	Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch). ICML Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2021	B	`conf`	Learning a mixture of two subspaces over finite fields. ALT Aidao Chen, Anindya De, Aravindan Vijayaraghavan
2020	A*	`conf`	Adversarial robustness via robust low rank representations. NeurIPS Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, Aravindan Vijayaraghavan
2020	J	`jnl`	Adversarial robustness via robust low rank representations. CoRR Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, Aravindan Vijayaraghavan
2020	J	`jnl`	Efficient Tensor Decomposition. CoRR Aravindan Vijayaraghavan
2020	—	`ch.`	Efficient Tensor Decompositions. Beyond the Worst-Case Analysis of Algorithms Aravindan Vijayaraghavan
2020	A*	`conf`	Estimating Principal Components under Adversarial Perturbations. COLT Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
2020	J	`jnl`	Estimating Principal Components under Adversarial Perturbations. CoRR Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan
2020	J	`jnl`	Graph cuts always find a global optimum (with a catch). CoRR Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2020	J	`jnl`	Learning a mixture of two subspaces over finite fields. CoRR Aidao Chen, Anindya De, Aravindan Vijayaraghavan
2020	A*	`conf`	Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. FOCS Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan
2020	J	`jnl`	Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. CoRR Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan
2019	J	`jnl`	Adversarially Robust Low Dimensional Representations. CoRR Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan
2019	A	`conf`	Block Stability for MAP Inference. AISTATS Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2019	A*	`conf`	On Robustness to Adversarial Examples and Polynomial Optimization. NeurIPS Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan
2019	J	`jnl`	On Robustness to Adversarial Examples and Polynomial Optimization. CoRR Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan
2019	A*	`conf`	Smoothed Analysis in Unsupervised Learning via Decoupling. FOCS Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan
2018	J	`jnl`	Block Stability for MAP Inference. CoRR Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2018	A*	`conf`	Clustering Semi-Random Mixtures of Gaussians. ICML Pranjal Awasthi, Aravindan Vijayaraghavan
2018	J	`jnl`	Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. ACM Trans. Algorithms Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang
2018	A	`conf`	Optimality of Approximate Inference Algorithms on Stable Instances. AISTATS Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2018	J	`jnl`	Smoothed Analysis in Unsupervised Learning via Decoupling. CoRR Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan
2018	A*	`conf`	Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. FOCS Pranjal Awasthi, Aravindan Vijayaraghavan
2018	J	`jnl`	Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. CoRR Pranjal Awasthi, Aravindan Vijayaraghavan
2017	J	`jnl`	Alpha-expansion is Exact on Stable Instances. CoRR Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan
2017	A*	`conf`	Approximation Algorithms for Label Cover and The Log-Density Threshold. SODA Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan
2017	J	`jnl`	Clustering Semi-Random Mixtures of Gaussians. CoRR Pranjal Awasthi, Aravindan Vijayaraghavan
2017	—	`conf`	Clustering Stable Instances of Euclidean k-means. NIPS Aravindan Vijayaraghavan, Abhratanu Dutta, Alex Wang
2017	J	`jnl`	Clustering Stable Instances of Euclidean k-means. CoRR Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang
2017	A*	`conf`	On Learning Mixtures of Well-Separated Gaussians. FOCS Oded Regev, Aravindan Vijayaraghavan
2017	J	`jnl`	On Learning Mixtures of Well-Separated Gaussians. CoRR Oded Regev, Aravindan Vijayaraghavan
2016	J	`jnl`	Approximation Algorithms and Hardness of the ACM Trans. Algorithms Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2016	A*	`conf`	Learning Communities in the Presence of Errors. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	—	`conf`	Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	A*	`conf`	Correlation Clustering with Noisy Partial Information. COLT Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2015	J	`jnl`	Learning Communities in the Presence of Errors. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Algorithms for Semi-random Correlation Clustering. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	A*	`conf`	Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	J	`jnl`	Constant Factor Approximation for Balanced Cut in the PIE model. CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	A*	`conf`	Constant factor approximation for balanced cut in the PIE model. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2014	—	`conf`	Learning Mixtures of Ranking Models. NIPS Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan
2014	J	`jnl`	Learning Mixtures of Ranking Models. CoRR Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan
2014	A*	`conf`	Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? COLT Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2014	A*	`conf`	Smoothed analysis of tensor decompositions. STOC Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2014	A*	`conf`	Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. COLT Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
2013	J	`jnl`	Bilu-Linial Stable Instances of Max Cut CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	J	`jnl`	Smoothed Analysis of Tensor Decompositions. CoRR Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan
2013	A	`conf`	Sorting noisy data with partial information. ITCS Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2013	J	`jnl`	Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability CoRR Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan
2012	J	`jnl`	Approximation Algorithms for Semi-random Graph Partitioning Problems CoRR Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	A*	`conf`	Approximation algorithms and hardness of the SODA Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2012	A*	`conf`	Approximation algorithms for semi-random partitioning problems. STOC Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
2012	—	`—`	Beyond Worst Case Analysis in Approximation Algorithms Aravindan Vijayaraghavan
2012	—	`conf`	On Quadratic Programming with a Ratio Objective. ICALP (1) Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan
2012	A*	`conf`	Polynomial integrality gaps for strong SDP relaxations of Densest SODA Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou
2011	A*	`conf`	Approximating Matrix p-norms. SODA Aditya Bhaskara, Aravindan Vijayaraghavan
2011	J	`jnl`	Approximation Algorithms and Hardness of the k-Route Cut Problem CoRR Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
2011	J	`jnl`	On Quadratic Programming with a Ratio Objective CoRR Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan
2011	J	`jnl`	Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph CoRR Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou
2010	J	`jnl`	Computing the Matrix p-norm CoRR Aditya Bhaskara, Aravindan Vijayaraghavan
2010	J	`jnl`	Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph CoRR Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan
2010	A*	`conf`	Detecting high log-densities: an STOC Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan