Faculty Directory
Aravindan Vijayaraghavan

Assistant Professor of Computer Science


2233 Tech Drive
Mudd Room 3011
Evanston, IL 60208-3109

847-467-6145Email Aravindan Vijayaraghavan


Aravindan Vijayaraghavan Homepage


Computer Science

Download CV


Ph.D Computer Science, Princeton University

M.A. Computer Science, Princeton University

B. Tech. Computer Science and Engineering,  Indian Institute of Technology, Madras

Research Interests

His research interests are broadly in the field of Theoretical Computer Science, particularly, in designing efficient algorithms for problems in Combinatorial Optimization and Machine Learning. He is also interested in using paradigms that go Beyond Worst-Case Analysis to obtain good algorithmic guarantees.

Selected Publications

    • Towards Learning Sparsely Used Dictionaries with Arbitrary Supports 
      (With Pranjal Awasthi). FOCS 2018. 
    • Clustering Semi-Random Mixtures of Gaussians 
      (With Pranjal Awasthi). ICML 2018. 
    • Optimality of Approximate Inference Algorithms on Stable Instances 
      (With Hunter Lang and David Sontag). AISTATS 2018. 
    • On Learning Mixtures of Well-Separated Gaussians . FOCS 2017(With Oded Regev). 
    • Clustering Stable Instances of Euclidean k-means. NIPS 2017. (With Abhratanu Dutta and Alex Wang).
    • Approximation Algorithms for Label Cover and the Log-Density Threshold. SODA 2017. (with Eden Chlamtac, Pasin Manurangsi and Dana Moshkovitz).  
    • Learning Communities in the Presence of Errors. COLT 2016. 
      (With Konstantin Makarychev and Yury Makarychev). 
    • Constant Factor Approximations for Balanced Cut in the random PIE model.STOC 2014.
    • (With Konstantin Makarychev and Yury Makarychev). [ Abstract]
    • Smoothed Analysis of Tensor DecompositionsSTOC 2014.
      (With Aditya Bhaskara, Moses Charikar and Ankur Moitra).
    • Bilu-Linial Stable Instances of Max Cut and Minimum Multiway CutSODA 2014.
      (With Konstantin Makarychev and Yury Makarychev).
    • Approximation algorithms for Semi-random Graph Partitioning problemsSTOC 2012
      (With Konstantin Makarychev and Yury Makarychev).
    • Approximating the matrix p-norm. SODA 2011. 
      (With Aditya Bhaskara) 
    • Detecting High Log-Densities -- an O(n1/4) Approximation for Densest k-SubgraphSTOC 2010
      (With Aditya Bhaskara, Moses Charikar, Eden Chlamtac and Uri Feige).