Aravindan Vijayaraghavan

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 65

Top Topics

Constant Factor Approximation

Tensor Decomposition

Top Venues

Publications

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