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

Distributed Clustering via LSH Based Data Partitioning
(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 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)
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)