A randomized scheduler with probabilistic guarantees of finding bugs S Burckhardt, P Kothari, M Musuvathi, S Nagarakatte ACM SIGARCH Computer Architecture News 38 (1), 167-178, 2010 | 327 | 2010 |
Differentially private online learning P Jain, P Kothari, A Thakurta Conference on Learning Theory, 24.1-24.34, 2012 | 269 | 2012 |
A nearly tight sum-of-squares lower bound for the planted clique problem B Barak, S Hopkins, J Kelner, PK Kothari, A Moitra, A Potechin SIAM Journal on Computing 48 (2), 687-735, 2019 | 259 | 2019 |
Robust moment estimation and improved clustering via sum of squares PK Kothari, J Steinhardt, D Steurer Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing …, 2018 | 191* | 2018 |
Efficient algorithms for outlier-robust regression A Klivans, PK Kothari, R Meka Conference on Learning Theory, COLT, 2018, 2018 | 174 | 2018 |
An analysis of the t-sne algorithm for data visualization S Arora, W Hu, PK Kothari Conference On Learning Theory, COLT 2018, 2018 | 173 | 2018 |
The power of sum-of-squares for detecting hidden structures SB Hopkins, PK Kothari, A Potechin, P Raghavendra, T Schramm, ... 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS …, 2017 | 150 | 2017 |
Sum of squares lower bounds for refuting any CSP PK Kothari, R Mori, R O'Donnell, D Witmer Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 114 | 2017 |
Semialgebraic Proofs and Efficient Algorithm Design. N Fleming, P Kothari, T Pitassi NOW the essence of knowledge, Foundations and Trends Series, 2019 | 84 | 2019 |
List-decodable linear regression S Karmalkar, AR Klivans, PK Kothari Advances in Neural Information Processing Systems, 2019 | 81 | 2019 |
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs PK Kothari, R Meka, P Raghavendra Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 74* | 2017 |
Provable submodular minimization using Wolfe's algorithm D Chakrabarty, P Jain, P Kothari Advances in Neural Information Processing Systems 27, 2014 | 74 | 2014 |
Sos and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four SB Hopkins, PK Kothari, A Potechin ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, 2015 | 65* | 2015 |
Robustly learning mixtures of k arbitrary Gaussians A Bakshi, I Diakonikolas, H Jia, DM Kane, PK Kothari, SS Vempala Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing …, 2022 | 64 | 2022 |
Outlier-robust moment-estimation via sum-of-squares PK Kothari, D Steurer Symposium on Theory of Computing, STOC 2018, 2017 | 63 | 2017 |
Outlier-Robust Clustering of Non-Spherical Mixtures A Bakshi, P Kothari IEEE Foundations of Computer Science, FOCS 2020, 2020 | 60* | 2020 |
Embedding hard learning problems into gaussian space A Klivans, P Kothari Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2014 | 57 | 2014 |
Submodular functions are noise stable M Cheraghchi, A Klivans, P Kothari, HK Lee ACM SIAM Symposium on Discrete Algorithms, SODA 2012, 2011 | 57 | 2011 |
Small-set expansion in shortcode graph and the 2-to-2 conjecture B Barak, PK Kothari, D Steurer Innovations in Theoretical Computer Science, ITCS, 2018 | 54 | 2018 |
Private robust estimation by stabilizing convex relaxations P Kothari, P Manurangsi, A Velingker Conference on Learning Theory, 723-777, 2022 | 52 | 2022 |