## 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 theory

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

(with Ananda Theertha Suresh and Morteza Zadimoghaddam)

To appear in 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, clustering, approximation

**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)

To appear in 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)