Research
I am broadly interested in theoretical computer science and machine learning. Here are some of my publications/manuscripts, ordered by topic and date.
Learning, clustering, and friends
Tight Bounds for Volumetric Spanners and Applications [PDF]
(with Sepideh Mahabadi and Ali Vakilian)
Advances in Neural Information Processing Systems (NeurIPS 2023)
Bandit Online Linear Optimization with Hints and Queries [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
International Conference on Machine Learning (ICML 2023)
Online Learning and Bandits with Queried Hints [PDF]
(with Sreenivas Gollapudi, Sungjin Im, Kostas Kollias and Kamesh Munagala)
Proceedings of the 14th Conference on Innovations in Theoretical Computer Science (ITCS 2023)
Structure of Nonlinear Node Embeddings in Stochastic Block Models [PDF]
(with Christopher Harker)
The 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)
Competing against Adaptive Strategies in Online Learning via Hints [PDF]
(with Kamesh Munagala)
The 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)
Logarithmic Regret from Sublinear Hints [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Advances in Neural Information Processing Systems (NeurIPS 2021)
Additive Error Guarantees for Weighted Low Rank Approximation [PDF]
(with Kanchana Ruwanpathirana and Maheshakya Wijewardena)
Proceedings of the 38th International Conference on Machine Learning (ICML 2021)
Fair Clustering via Equitable Group Representations [PDF]
(with Mohsen Abbassi and Suresh Venkatasubramanian)
ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT 2021)
Principal Component Regression with Semirandom Observations via Matrix Completion [PDF]
(with Kanchana Ruwanpathirana and Maheshakya Wijewardena)
The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
Power of Hints for Online Learning with Movement Costs
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
Online MAP Inference of Determinantal Point Processes [PDF]
(with Amin Karbasi, Silvio Lattanzi and Morteza Zadimoghaddam)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Online Linear Optimization with Many Hints [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Adaptive Probing Policies for Shortest Path Routing [PDF]
(with Sreenivas Gollapudi, Kamesh Munagala and Kostas Kollias)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Online Learning with Imperfect Hints [Arxiv] [Video -- Ravi at the STOC Workshop on Algorithms with Predictions]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Proceedings of the 37th International Conference on Machine Learning (ICML 2020)
Robust Algorithms for Online k-means Clustering [PDF]
(with Kanchana Ruwanpathirana)
Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT 2020)
Greedy Sampling for Approximate Clustering in the Presence of Outliers [PDF]
(with Sharvaree Vadgama and Hong Xu)
Advances in Neural Information Processing Systems (NeurIPS 2019)
On Distributed Averaging for Stochastic k-PCA [PDF]
(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)
(with Sepideh Mahabadi and Ali Vakilian)
Advances in Neural Information Processing Systems (NeurIPS 2023)
Bandit Online Linear Optimization with Hints and Queries [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
International Conference on Machine Learning (ICML 2023)
Online Learning and Bandits with Queried Hints [PDF]
(with Sreenivas Gollapudi, Sungjin Im, Kostas Kollias and Kamesh Munagala)
Proceedings of the 14th Conference on Innovations in Theoretical Computer Science (ITCS 2023)
Structure of Nonlinear Node Embeddings in Stochastic Block Models [PDF]
(with Christopher Harker)
The 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)
Competing against Adaptive Strategies in Online Learning via Hints [PDF]
(with Kamesh Munagala)
The 26th International Conference on Artificial Intelligence and Statistics (AISTATS 2023)
Logarithmic Regret from Sublinear Hints [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Advances in Neural Information Processing Systems (NeurIPS 2021)
Additive Error Guarantees for Weighted Low Rank Approximation [PDF]
(with Kanchana Ruwanpathirana and Maheshakya Wijewardena)
Proceedings of the 38th International Conference on Machine Learning (ICML 2021)
Fair Clustering via Equitable Group Representations [PDF]
(with Mohsen Abbassi and Suresh Venkatasubramanian)
ACM Conference on Fairness, Accountability, and Transparency (ACM FAccT 2021)
Principal Component Regression with Semirandom Observations via Matrix Completion [PDF]
(with Kanchana Ruwanpathirana and Maheshakya Wijewardena)
The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
Power of Hints for Online Learning with Movement Costs
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
The 24th International Conference on Artificial Intelligence and Statistics (AISTATS 2021)
Online MAP Inference of Determinantal Point Processes [PDF]
(with Amin Karbasi, Silvio Lattanzi and Morteza Zadimoghaddam)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Online Linear Optimization with Many Hints [PDF]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Adaptive Probing Policies for Shortest Path Routing [PDF]
(with Sreenivas Gollapudi, Kamesh Munagala and Kostas Kollias)
Advances in Neural Information Processing Systems (NeurIPS 2020)
Online Learning with Imperfect Hints [Arxiv] [Video -- Ravi at the STOC Workshop on Algorithms with Predictions]
(with Ashok Cutkosky, Ravi Kumar and Manish Purohit)
Proceedings of the 37th International Conference on Machine Learning (ICML 2020)
Robust Algorithms for Online k-means Clustering [PDF]
(with Kanchana Ruwanpathirana)
Proceedings of the 31st International Conference on Algorithmic Learning Theory (ALT 2020)
Greedy Sampling for Approximate Clustering in the Presence of Outliers [PDF]
(with Sharvaree Vadgama and Hong Xu)
Advances in Neural Information Processing Systems (NeurIPS 2019)
On Distributed Averaging for Stochastic k-PCA [PDF]
(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 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)
(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
A Plug-n-Play Game Theoretic Framework For Defending Against Radio Window Attacks
(with Maheshakya Wijewardena (first author), Sneha Kasera, Syed Ayaz Mahmud and Neal Patwari)
Proceedings of the 13th ACM Conference on Security and Privacy in Wireless and Mobile Networks (ACM WiSec 2020)
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)
(with Maheshakya Wijewardena (first author), Sneha Kasera, Syed Ayaz Mahmud and Neal Patwari)
Proceedings of the 13th ACM Conference on Security and Privacy in Wireless and Mobile Networks (ACM WiSec 2020)
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)