default search action
Aravindan Vijayaraghavan
Person information
- affiliation: Northwestern University, Evanston, IL, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
- [c45]Jinshuo Dong
, Jason D. Hartline
Error-Tolerant E-Discovery Protocols. CSLAW 2024: 24-35 - [c44]Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. FOCS 2024: 970-987 - [c43]Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan:
Higher-Order Cheeger Inequality for Partitioning with Buffers. SODA 2024: 2236-2274 - [c42]Aditya Bhaskara
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. STOC 2024: 375-386 - [i43]Jinshuo Dong, Jason D. Hartline, Liren Shan, Aravindan Vijayaraghavan:
Error-Tolerant E-Discovery Protocols. CoRR abs/2401.17952 (2024) - [i42]Aditya Bhaskara, Eric Evert, Vaidehi Srinivas, Aravindan Vijayaraghavan:
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries. CoRR abs/2405.01517 (2024) - [i41]Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan:
Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR abs/2405.15084 (2024) - [i40]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Theoretical Analysis of Weak-to-Strong Generalization. CoRR abs/2405.16043 (2024) - 2023
- [c41]Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan:
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. FOCS 2023: 1316-1336 - [c40]Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan:
Agnostic Learning of General ReLU Activation Using Gradient Descent. ICLR 2023 - [i39]Konstantin Makarychev, Yury Makarychev, Liren Shan, Aravindan Vijayaraghavan:
Higher-Order Cheeger Inequality for Partitioning with Buffers. CoRR abs/2308.10160 (2023) - [i38]Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan:
A hierarchy of eigencomputations for polynomial optimization on the sphere. CoRR abs/2310.17827 (2023) - 2022
- [j3]Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan
Smoothed analysis for tensor methods in unsupervised learning. Math. Program. 193(2): 549-599 (2022) - [c39]Pranjal Awasthi, Sivaraman Balakrishnan, Aravindan Vijayaraghavan:
Understanding Simultaneous Train and Test Robustness. ALT 2022: 34-69 - [c38]Aidao Chen, Anindya De, Aravindan Vijayaraghavan:
Algorithms for learning a mixture of linear classifiers. ALT 2022: 205-226 - [c37]Jinshuo Dong, Jason D. Hartline, Aravindan Vijayaraghavan:
Classification Protocols with Minimal Disclosure. CSLAW 2022: 67-76 - [c36]Patrick O'Reilly, Pranjal Awasthi, Aravindan Vijayaraghavan, Bryan Pardo:
Effective and Inconspicuous Over-the-Air Adversarial Examples with Adaptive Filtering. ICASSP 2022: 6607-6611 - [c35]Hunter Lang, Aravindan Vijayaraghavan, David A. Sontag:
Training Subset Selection for Weak Supervision. NeurIPS 2022 - [c34]Liam O'Carroll, Vaidehi Srinivas, Aravindan Vijayaraghavan:
The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound. NeurIPS 2022 - [i37]Hunter Lang, Aravindan Vijayaraghavan, David A. Sontag:
Training Subset Selection for Weak Supervision. CoRR abs/2206.02914 (2022) - [i36]Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan:
Agnostic Learning of General ReLU Activation Using Gradient Descent. CoRR abs/2208.02711 (2022) - [i35]Jinshuo Dong, Jason D. Hartline, Aravindan Vijayaraghavan:
Classification Protocols with Minimal Disclosure. CoRR abs/2209.02690 (2022) - [i34]Liam O'Carroll, Vaidehi Srinivas, Aravindan Vijayaraghavan:
The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound. CoRR abs/2211.12389 (2022) - [i33]Nathaniel Johnston, Benjamin Lovitz, Aravindan Vijayaraghavan:
Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. CoRR abs/2212.03851 (2022) - 2021
- [c33]Hunter Lang, Aravind Reddy, David A. Sontag, Aravindan Vijayaraghavan:
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances. AISTATS 2021: 3043-3051 - [c32]Aidao Chen, Anindya De, Aravindan Vijayaraghavan:
Learning a mixture of two subspaces over finite fields. ALT 2021: 481-504 - [c31]Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan:
Adversarially Robust Low Dimensional Representations. COLT 2021: 237-325 - [c30]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Graph Cuts Always Find a Global Optimum for Potts Models (With a Catch). ICML 2021: 5990-5999 - [c29]Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan:
Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. NeurIPS 2021: 13485-13496 - [i32]Hunter Lang, Aravind Reddy, David A. Sontag, Aravindan Vijayaraghavan:
Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances. CoRR abs/2103.00034 (2021) - [i31]Pranjal Awasthi, Alex Tang, Aravindan Vijayaraghavan:
Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations. CoRR abs/2107.10209 (2021) - 2020
- [c28]Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan:
Estimating Principal Components under Adversarial Perturbations. COLT 2020: 323-362 - [c27]Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan:
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. FOCS 2020: 834-845 - [c26]Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, Aravindan Vijayaraghavan:
Adversarial robustness via robust low rank representations. NeurIPS 2020 - [p1]Aravindan Vijayaraghavan:
Efficient Tensor Decompositions. Beyond the Worst-Case Analysis of Algorithms 2020: 424-444 - [i30]Biswaroop Maiti, Rajmohan Rajaraman, David Stalfa, Zoya Svitkina, Aravindan Vijayaraghavan:
Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay. CoRR abs/2004.10776 (2020) - [i29]Pranjal Awasthi, Xue Chen, Aravindan Vijayaraghavan:
Estimating Principal Components under Adversarial Perturbations. CoRR abs/2006.00602 (2020) - [i28]Pranjal Awasthi, Himanshu Jain, Ankit Singh Rawat, Aravindan Vijayaraghavan:
Adversarial robustness via robust low rank representations. CoRR abs/2007.06555 (2020) - [i27]Aravindan Vijayaraghavan:
Efficient Tensor Decomposition. CoRR abs/2007.15589 (2020) - [i26]Aidao Chen, Anindya De, Aravindan Vijayaraghavan:
Learning a mixture of two subspaces over finite fields. CoRR abs/2010.02841 (2020) - [i25]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Graph cuts always find a global optimum (with a catch). CoRR abs/2011.03639 (2020)
2010 – 2019
- 2019
- [c25]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Block Stability for MAP Inference. AISTATS 2019: 216-225 - [c24]Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan:
Smoothed Analysis in Unsupervised Learning via Decoupling. FOCS 2019: 582-610 - [c23]Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan:
On Robustness to Adversarial Examples and Polynomial Optimization. NeurIPS 2019: 13737-13747 - [i24]Pranjal Awasthi, Abhratanu Dutta, Aravindan Vijayaraghavan:
On Robustness to Adversarial Examples and Polynomial Optimization. CoRR abs/1911.04681 (2019) - [i23]Pranjal Awasthi, Vaggos Chatziafratis, Xue Chen, Aravindan Vijayaraghavan:
Adversarially Robust Low Dimensional Representations. CoRR abs/1911.13268 (2019) - 2018
- [j2]Arnab Bhattacharyya, Fabrizio Grandoni
Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue. ACM Trans. Algorithms 14(3): 26:1-26:2 (2018) - [c22]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Optimality of Approximate Inference Algorithms on Stable Instances. AISTATS 2018: 1157-1166 - [c21]Pranjal Awasthi, Aravindan Vijayaraghavan:
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. FOCS 2018: 283-296 - [c20]Pranjal Awasthi, Aravindan Vijayaraghavan:
Clustering Semi-Random Mixtures of Gaussians. ICML 2018: 294-303 - [i22]Pranjal Awasthi, Aravindan Vijayaraghavan:
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports. CoRR abs/1804.08603 (2018) - [i21]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Block Stability for MAP Inference. CoRR abs/1810.05305 (2018) - [i20]Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan:
Smoothed Analysis in Unsupervised Learning via Decoupling. CoRR abs/1811.12361 (2018) - 2017
- [c19]Oded Regev, Aravindan Vijayaraghavan:
On Learning Mixtures of Well-Separated Gaussians. FOCS 2017: 85-96 - [c18]Aravindan Vijayaraghavan, Abhratanu Dutta, Alex Wang:
Clustering Stable Instances of Euclidean k-means. NIPS 2017: 6500-6509 - [c17]Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan:
Approximation Algorithms for Label Cover and The Log-Density Threshold. SODA 2017: 900-919 - [i19]Oded Regev, Aravindan Vijayaraghavan:
On Learning Mixtures of Well-Separated Gaussians. CoRR abs/1710.11592 (2017) - [i18]Hunter Lang, David A. Sontag, Aravindan Vijayaraghavan:
Alpha-expansion is Exact on Stable Instances. CoRR abs/1711.02195 (2017) - [i17]Pranjal Awasthi, Aravindan Vijayaraghavan:
Clustering Semi-Random Mixtures of Gaussians. CoRR abs/1711.08841 (2017) - [i16]Abhratanu Dutta, Aravindan Vijayaraghavan, Alex Wang:
Clustering Stable Instances of Euclidean k-means. CoRR abs/1712.01241 (2017) - 2016
- [j1]Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou:
Approximation Algorithms and Hardness of the k-Route Cut Problem. ACM Trans. Algorithms 12(1): 2:1-2:40 (2016) - [c16]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Learning Communities in the Presence of Errors. COLT 2016: 1258-1291 - 2015
- [c15]Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer
Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM 2015: 110-123 - [c14]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Correlation Clustering with Noisy Partial Information. COLT 2015: 1321-1342 - [i15]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 abs/1505.03424 (2015) - [i14]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Learning Communities in the Presence of Errors. CoRR abs/1511.03229 (2015) - [i13]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. TR15 (2015) - 2014
- [c13]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan:
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. COLT 2014: 742-778 - [c12]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Open Problem: Tensor Decompositions: Algorithms up to the Uniqueness Threshold? COLT 2014: 1280-1282 - [c11]Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan:
Learning Mixtures of Ranking Models. NIPS 2014: 2609-2617 - [c10]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Bilu-Linial Stable Instances of Max Cut and Minimum Multiway Cut. SODA 2014: 890-906 - [c9]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Constant factor approximation for balanced cut in the PIE model. STOC 2014: 41-49 - [c8]Aditya Bhaskara, Moses Charikar
Smoothed analysis of tensor decompositions. STOC 2014: 594-603 - [i12]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Constant Factor Approximation for Balanced Cut in the PIE model. CoRR abs/1406.5665 (2014) - [i11]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Algorithms for Semi-random Correlation Clustering. CoRR abs/1406.5667 (2014) - [i10]Pranjal Awasthi, Avrim Blum, Or Sheffet, Aravindan Vijayaraghavan:
Learning Mixtures of Ranking Models. CoRR abs/1410.8750 (2014) - 2013
- [c7]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Sorting noisy data with partial information. ITCS 2013: 515-528 - [i9]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan:
Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability. CoRR abs/1304.8087 (2013) - [i8]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Bilu-Linial Stable Instances of Max Cut. CoRR abs/1305.1681 (2013) - [i7]Aditya Bhaskara, Moses Charikar, Ankur Moitra, Aravindan Vijayaraghavan:
Smoothed Analysis of Tensor Decompositions. CoRR abs/1311.3651 (2013) - 2012
- [b1]Aravindan Vijayaraghavan:
Beyond Worst Case Analysis in Approximation Algorithms. Princeton University, USA, 2012 - [c6]Aditya Bhaskara, Moses Charikar
On Quadratic Programming with a Ratio Objective. ICALP (1) 2012: 109-120 - [c5]Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, Yuan Zhou
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. SODA 2012: 388-405 - [c4]Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
Approximation algorithms and hardness of the k-route cut problem. SODA 2012: 780-799 - [c3]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Approximation algorithms for semi-random partitioning problems. STOC 2012: 367-384 - [i6]Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan:
Approximation Algorithms for Semi-random Graph Partitioning Problems. CoRR abs/1205.2234 (2012) - 2011
- [c2]Aditya Bhaskara, Aravindan Vijayaraghavan:
Approximating Matrix p-norms. SODA 2011: 497-511 - [i5]Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan:
On Quadratic Programming with a Ratio Objective. CoRR abs/1101.1710 (2011) - [i4]Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou:
Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. CoRR abs/1110.1360 (2011) - [i3]Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou:
Approximation Algorithms and Hardness of the k-Route Cut Problem. CoRR abs/1112.3611 (2011) - 2010
- [c1]Aditya Bhaskara, Moses Charikar
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. STOC 2010: 201-210 - [i2]Aditya Bhaskara, Aravindan Vijayaraghavan:
Computing the Matrix p-norm. CoRR abs/1001.2613 (2010) - [i1]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 abs/1001.2891 (2010)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-10 21:48 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: