## Research

I am broadly interested in theoretical computer science and machine learning. Here are some of my publications/manuscripts (ordered by topic), with informal abstracts.

### Learning, clustering, and friends

**Greedy Sampling for Approximate Clustering in the Presence of Outliers**

(with Sharvaree Vadgama and Hong Xu)

Advances in Neural Information Processing Systems (NeurIPS 2019)

**On Distributed Averaging for Stochastic k-PCA**

(with Maheshakya Wijewardena)

Advances in Neural Information Processing Systems (NeurIPS 2019)

**Residual Based Sampling for Online Low Rank Approximation**[PDF] [talk at Simons Institute]

(with Silvio Lattanzi, Sergei Vassilvitskii and Morteza Zadimoghaddam)

Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019)

**Smoothed Analysis in Unsupervised Learning via Decoupling**[arxiv]

(with Aidao Chen, Aidan Perrault and Aravindan Vijayaraghavan)

Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019)

**Approximate Guarantees for Dictionary Learning**[arxiv]

(with Wai-Ming Tai)

Proceedings of the 32nd Annual Conference on Learning Theory (COLT 2019)

**Distributed Clustering via LSH Based Data Partitioning**[PDF]

(with Maheshakya Wijewardena)

Proceedings of the 35th International Conference on Machine Learning (ICML 2018)

**Low Rank Approximation in the Presence of Outliers**[Arxiv]

(with Srivatsan Kumar)

Proceedings of the 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2018)

**Non-negative Sparse Regression and Column Selection with L1 Error**[PDF]

(with Silvio Lattanzi)

Proceedings of the 9th Conference on Innovations in Theoretical Computer Science (ITCS 2018)

**On Binary Embedding using Circulant Matrices**[PDF]

(with Felix Yu, Sanjiv Kumar, Yunchao Gong and Shih-Fu Chang)

Journal of Machine Learning Research (JMLR), 2018

**Greedy Column Subset Selection: New Bounds and Distributed Algorithms**[PDF]

(with Jason Altschuler, Gang (Thomas) Fu, Vahab Mirrokni, Afshin Rostamizadeh and Morteza Zadimoghaddam)

Proceedings of the 33rd International Conference on Machine Machine Learning (ICML 2016)

**Sparse Solutions to Nonnegative Linear Systems and Applications**[PDF] [abs]

(with Ananda Theertha Suresh and Morteza Zadimoghaddam)

Proceedings of the 18th International Conference on Artificial Intelligence and Statistics (AISTATS 2015)

**Smoothed Analysis of Tensor Decomposition**[PDF] [abs]

(with Moses Charikar, Ankur Moitra and Aravindan Vijayaraghavan)

Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014)

**Uniqueness of Tensor Decompositions and Identifiability in Latent Variable Models**[PDF] [abs]

(with Moses Charikar and Aravindan Vijayaraghavan)

Proceedings of the 27th Annual Conference on Learning Theory (COLT 2014)

**Provable Bounds for Learning Some Deep Representations**[PDF] [abs]

(with Sanjeev Arora, Rong Ge and Tengyu Ma)

Proceedings of the 31st International Conference on Machine Learning (ICML 2014)

**Provable Dictionary Learning via Column Signatures**[PDF] [abs]

(with Sanjeev Arora, Rong Ge and Tengyu Ma)

Manuscript (2014)

### Graph algorithms, approximation

**Sublinear Algorithms for MAXCUT and Correlation Clustering**[Arxiv]

(with Samira Daruki and Suresh Venkatasubramanian)

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

**Linear Relaxations for Finding Diverse Elements in Metric Spaces**[PDF]

(with Mehrdad Ghadiri, Vahab Mirrokni and Ola Svensson)

To appear in Advances in Neural Information Processing Systems (NIPS 2016)

**Expanders via Local Edge Flips**[PDF] [abs]

(with Zeyuan Allen-Zhou, Silvio Lattanzi, Vahab Mirrokni and Lorenzo Orecchia)

Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016). Also featured in the Highlights of Algorithms conference (HALG 2017).

**Centrality of Trees for Capacitated**[PDF] [abs]

*k*-Center(with Hyung-Chan An, Chandra Chekuri, Shalmoli Gupta, Vivek Madan and Ola Svensson)

Proceedings of the 17th Conference on Integer Programming and Combinatorial Optimization (IPCO 2014)

**Distributed Balanced Clustering via Mapping Coresets**[PDF] [abs]

(with MohammadHossein Bateni, Silvio Lattanzi and Vahab Mirrokni)

Advances in Neural Information Processing Systems (NIPS 2014)

**On Quadratic Programming with a Ratio Objective**[PDF]

(with Moses Charikar, Rajsekar Manokaran and Aravindan Vijayaraghavan)

Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)

**Polynomial Integrality gaps for Strong relaxations of Densest**[PDF] [abs]

*k*-subgraph(with Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, and Yuan Zhou)

Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)

**Approximating Matrix**[PDF] [abs]

*p*-norms(with Aravindan Vijayaraghavan)

Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)

**Detecting High Log-densities: An O(n^(1/4)) Approximation for Densest**[PDF] [abs]

*k*-Subgraph(with Moses Charikar, Eden Chlamtac, Uriel Feige and Aravindan Vijayaraghavan)

Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC 2010)

### Other topics

**Optimizing Display Advertising in Online Social Networks**[PDF]

(with Zeinab Abbassi and Vishal Misra)

Proceedings of the 24th International World Wide Web Conference (WWW 2015)

**Minimum Makespan Scheduling with Low Rank Processing Times**[PDF] [abs]

(with Ravishankar Krishnaswamy, Kunal Talwar and Udi Wieder)

Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

**Unconditional Differentially Private Mechanisms for Linear Queries**[PDF] [abs]

(with Daniel Dadush, Ravishankar Krishnaswamy and Kunal Talwar)

Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012)

**Optimal Hitting Sets for Combinatorial Shapes**[PDF] [abs]

(with Devendra Desai and Srikanth Srinivasan)

Proceedings of the 16th International Workshop on Randomization and Computation (RANDOM 2012)

*(invited to a special issue of Theory of Computing)*

**Eigenvectors of Random Graphs: Delocalization and Nodal Domains**[PDF]

(with Sanjeev Arora)

Manuscript (2011)

**A note on the Lovasz theta number of random graphs**[PDF]

(with Sanjeev Arora)

Manuscript (2011)