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 k-Center [PDF] [abs]
(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 k-subgraph [PDF] [abs]
(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 p-norms [PDF] [abs]
(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 k-Subgraph [PDF] [abs]
(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)