| 2026 | COLT | Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures. | Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer |
| 2026 | SODA | Sparsifying Sums of Positive Semidefinite Matrices. | Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka |
| 2026 | SODA | Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. | Pravesh K. Kothari, Jeff Xu |
| 2026 | STOC | SNARGs for NP and Non-signaling PCPs, Revisited. | Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan |
| 2026 | STOC | Rigorous Implications of the Low-Degree Heuristic. | Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel |
| 2026 | STOC | Learning Mixture Models via Efficient High-Dimensional Sparse Fourier Transforms. | Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis |
| 2025 | FOCS | Improved Lower Bounds for all Odd-Query Locally Decodable Codes. | Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin |
| 2025 | FOCS | The Quasi-Polynomial Low-Degree Conjecture is False. | Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari |
| 2025 | FOCS | Overcomplete Tensor Decomposition via Koszul-Young Flattenings. | Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein |
| 2025 | STOC | Rounding Large Independent Sets on Expanders. | Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari |
| 2024 | FOCS | Efficient Certificates of Anti-Concentration Beyond Gaussians. | Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan |
| 2024 | FOCS | Semirandom Planted Clique and the Restricted Isometry Property. | Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer |
| 2024 | FOCS | Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. | Pravesh K. Kothari, Peter Manohar |
| 2024 | SODA | New SDP Roundings and Certifiable Approximation for Cubic Optimization. | Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan |
| 2024 | STOC | An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. | Pravesh K. Kothari, Peter Manohar |
| 2024 | STOC | Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. | Pravesh K. Kothari, Aaron Potechin, Jeff Xu |
| 2023 | FOCS | Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. | Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar |
| 2023 | FOCS | Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. | He Jia, Pravesh K. Kothari, Santosh S. Vempala |
| 2023 | ICALP | Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. | Jun-Ting Hsieh, Pravesh K. Kothari |
| 2023 | ICALP | Ellipsoid Fitting up to a Constant. | Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu |
| 2023 | SODA | A simple and sharper proof of the hypergraph Moore bound. | Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty |
| 2023 | STOC | Privately Estimating a Gaussian: Efficient, Robust, and Optimal. | Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang |
| 2023 | STOC | A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. | Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2023 | STOC | Algorithms Approaching the Threshold for Semi-random Planted Clique. | Rares-Darius Buhai, Pravesh K. Kothari, David Steurer |
| 2023 | STOC | A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. | Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari |
| 2023 | TCC | Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. | Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen |
| 2022 | ALT | Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. | Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang |
| 2022 | FOCS | Polynomial-Time Power-Sum Decomposition of Polynomials. | Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu |
| 2022 | SODA | Algorithmic Thresholds for Refuting Random Polynomial Systems. | Jun-Ting Hsieh, Pravesh K. Kothari |
| 2022 | STOC | Robustly learning mixtures of | Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala |
| 2022 | STOC | Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. | Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar |
| 2022 | STOC | List-decodable covariance estimation. | Misha Ivkov, Pravesh K. Kothari |
| 2021 | SODA | Strongly refuting all semi-random Boolean CSPs. | Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari |
| 2021 | SODA | List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. | Ainesh Bakshi, Pravesh K. Kothari |
| 2021 | STOC | Playing unique games on certified small-set expanders. | Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer |
| 2020 | ALT | On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. | Pravesh K. Kothari, Roi Livni |
| 2020 | FOCS | Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. | Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari |
| 2020 | FOCS | Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. | Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer |
| 2019 | COMAD | The Social Network Effect on Surprise in Elections. | Palash Dey, Pravesh K. Kothari, Swaprava Nath |
| 2018 | COLT | An Analysis of the t-SNE Algorithm for Data Visualization. | Sanjeev Arora, Wei Hu, Pravesh K. Kothari |
| 2018 | COLT | Efficient Algorithms for Outlier-Robust Regression. | Adam R. Klivans, Pravesh K. Kothari, Raghu Meka |
| 2018 | EuroCrypt | Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). | Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari |
| 2018 | STOC | Sum-of-squares meets nash: lower bounds for finding any equilibrium. | Pravesh K. Kothari, Ruta Mehta |
| 2018 | STOC | Robust moment estimation and improved clustering via sum of squares. | Pravesh K. Kothari, Jacob Steinhardt, David Steurer |
| 2017 | FOCS | The Power of Sum-of-Squares for Detecting Hidden Structures. | Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer |
| 2017 | STOC | Quantum entanglement, sum of squares, and the log rank conjecture. | Boaz Barak, Pravesh K. Kothari, David Steurer |
| 2017 | STOC | Sum of squares lower bounds for refuting any CSP. | Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer |
| 2017 | STOC | Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. | Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra |
| 2015 | STOC | Sum of Squares Lower Bounds from Pairwise Independence. | Boaz Barak, Siu On Chan, Pravesh K. Kothari |
| 2015 | STOC | Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. | Pravesh K. Kothari, Raghu Meka |