Pravesh K. Kothari

109 papers A* 41A 5B 2Journal 56Unranked 5

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms. CoRR Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis
2026	J	`jnl`	Rigorous Implications of the Low-Degree Heuristic. CoRR Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari, Jerry Li, Sidhanth Mohanty, Stefan Tiegel
2026	J	`jnl`	SNARGs for NP and Non-Signaling PCPs, Revisited. IACR Cryptol. ePrint Arch. Lalita Devadas, Samuel B. Hopkins, Yael Tauman Kalai, Pravesh K. Kothari, Alex Lombardi, Surya Mathialagan
2026	A*	`conf`	Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. SODA Pravesh K. Kothari, Jeff Xu
2026	A*	`conf`	Sparsifying Sums of Positive Semidefinite Matrices. SODA Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka
2025	A*	`conf`	Improved Lower Bounds for all Odd-Query Locally Decodable Codes. FOCS Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin
2025	J	`jnl`	New Spectral Algorithms for Refuting Smoothed k-SAT. Commun. ACM Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2025	A*	`conf`	Overcomplete Tensor Decomposition via Koszul-Young Flattenings. FOCS Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
2025	A*	`conf`	Rounding Large Independent Sets on Expanders. STOC Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
2025	J	`jnl`	Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. CoRR Pravesh K. Kothari, Jeff Xu
2025	J	`jnl`	Sparsifying Sums of Positive Semidefinite Matrices. CoRR Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka
2025	J	`jnl`	Sum-Of-Squares To Approximate Knapsack. CoRR Pravesh K. Kothari, Sherry Sarkar
2025	A*	`conf`	The Quasi-Polynomial Low-Degree Conjecture is False. FOCS Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari
2025	J	`jnl`	The Quasi-Polynomial Low-Degree Conjecture is False. CoRR Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain, Pravesh K. Kothari
2024	A*	`conf`	An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. STOC Pravesh K. Kothari, Peter Manohar
2024	J	`jnl`	Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures. CoRR Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2024	A*	`conf`	Efficient Certificates of Anti-Concentration Beyond Gaussians. FOCS Ainesh Bakshi, Pravesh K. Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
2024	A*	`conf`	Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. FOCS Pravesh K. Kothari, Peter Manohar
2024	J	`jnl`	Improved Lower Bounds for all Odd-Query Locally Decodable Codes. CoRR Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari, Andrew D. Lin
2024	A*	`conf`	New SDP Roundings and Certifiable Approximation for Cubic Optimization. SODA Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
2024	J	`jnl`	Overcomplete Tensor Decomposition via Koszul-Young Flattenings. CoRR Pravesh K. Kothari, Ankur Moitra, Alexander S. Wein
2024	J	`jnl`	Rounding Large Independent Sets on Expanders. CoRR Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
2024	A*	`conf`	Semirandom Planted Clique and the Restricted Isometry Property. FOCS Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2024	J	`jnl`	Semirandom Planted Clique and the Restricted Isometry Property. CoRR Jaroslaw Blasiok, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2024	J	`jnl`	Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty, David Munhá Correia, Benny Sudakov
2024	A*	`conf`	Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. STOC Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2024	J	`jnl`	Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. CoRR Pravesh K. Kothari, Peter Manohar
2023	A*	`conf`	A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. STOC Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
2023	A*	`conf`	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. STOC Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. CoRR Omar Alrabiah, Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2023	A*	`conf`	A simple and sharper proof of the hypergraph Moore bound. SODA Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty
2023	A*	`conf`	Algorithms Approaching the Threshold for Semi-random Planted Clique. STOC Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2023	J	`jnl`	An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. CoRR Pravesh K. Kothari, Peter Manohar
2023	A*	`conf`	Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. ICALP Jun-Ting Hsieh, Pravesh K. Kothari
2023	A*	`conf`	Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. FOCS He Jia, Pravesh K. Kothari, Santosh S. Vempala
2023	A*	`conf`	Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. FOCS Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. CoRR Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar
2023	J	`jnl`	Ellipsoid Fitting Up to a Constant. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2023	A*	`conf`	Ellipsoid Fitting up to a Constant. ICALP Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu
2023	J	`jnl`	Is Planted Coloring Easier than Planted Clique? CoRR Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
2023	J	`jnl`	New SDP Roundings and Certifiable Approximation for Cubic Optimization. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Lucas Pesenti, Luca Trevisan
2023	A*	`conf`	Privately Estimating a Gaussian: Efficient, Robust, and Optimal. STOC Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang
2023	—	`conf`	Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. TCC (1) Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen
2022	J	`jnl`	A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. CoRR Aravind Gollakota, Adam R. Klivans, Pravesh K. Kothari
2022	J	`jnl`	A simple and sharper proof of the hypergraph Moore bound. CoRR Jun-Ting Hsieh, Pravesh K. Kothari, Sidhanth Mohanty
2022	A*	`conf`	Algorithmic Thresholds for Refuting Random Polynomial Systems. SODA Jun-Ting Hsieh, Pravesh K. Kothari
2022	A*	`conf`	Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. STOC Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	J	`jnl`	Algorithms approaching the threshold for semi-random planted clique. CoRR Rares-Darius Buhai, Pravesh K. Kothari, David Steurer
2022	J	`jnl`	Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. CoRR Jun-Ting Hsieh, Pravesh K. Kothari
2022	J	`jnl`	Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. SIAM J. Comput. Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
2022	A	`conf`	Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. APPROX/RANDOM Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	J	`jnl`	Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. CoRR Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2022	J	`jnl`	List-Decodable Covariance Estimation. CoRR Misha Ivkov, Pravesh K. Kothari
2022	A*	`conf`	List-decodable covariance estimation. STOC Misha Ivkov, Pravesh K. Kothari
2022	A*	`conf`	Polynomial-Time Power-Sum Decomposition of Polynomials. FOCS Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu
2022	J	`jnl`	Polynomial-Time Power-Sum Decomposition of Polynomials. CoRR Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu
2022	B	`conf`	Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. ALT Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
2022	J	`jnl`	Privately Estimating a Gaussian: Efficient, Robust and Optimal. CoRR Daniel Alabi, Pravesh K. Kothari, Pranay Tankala, Prayaag Venkat, Fred Zhang
2022	A*	`conf`	Robustly learning mixtures of STOC Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
2021	A	`conf`	A Stress-Free Sum-Of-Squares Lower Bound for Coloring. CCC Pravesh K. Kothari, Peter Manohar
2021	J	`jnl`	A Stress-Free Sum-of-Squares Lower Bound for Coloring. CoRR Pravesh K. Kothari, Peter Manohar
2021	J	`jnl`	Algorithmic Thresholds for Refuting Random Polynomial Systems. CoRR Jun-Ting Hsieh, Pravesh K. Kothari
2021	J	`jnl`	Algorithms and Certificates for Boolean CSP Refutation: "Smoothed is no harder than Random". CoRR Venkatesan Guruswami, Pravesh K. Kothari, Peter Manohar
2021	A*	`conf`	List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. SODA Ainesh Bakshi, Pravesh K. Kothari
2021	—	`conf`	Memory-Sample Lower Bounds for Learning Parity with Noise. APPROX-RANDOM Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
2021	J	`jnl`	Memory-Sample Lower Bounds for Learning Parity with Noise. CoRR Sumegha Garg, Pravesh K. Kothari, Pengda Liu, Ran Raz
2021	A*	`conf`	Playing unique games on certified small-set expanders. STOC Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer
2021	J	`jnl`	Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. CoRR Pravesh K. Kothari, Peter Manohar, Brian Hu Zhang
2021	J	`jnl`	Private Robust Estimation by Stabilizing Convex Relaxations. CoRR Pravesh K. Kothari, Pasin Manurangsi, Ameya Velingker
2021	A*	`conf`	Strongly refuting all semi-random Boolean CSPs. SODA Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
2020	B	`conf`	On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. ALT Pravesh K. Kothari, Roi Livni
2020	A*	`conf`	Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. FOCS Ainesh Bakshi, Ilias Diakonikolas, Samuel B. Hopkins, Daniel Kane, Sushrut Karmalkar, Pravesh K. Kothari
2020	J	`jnl`	Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala
2020	A*	`conf`	Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. FOCS Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
2020	J	`jnl`	Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. CoRR Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer
2020	J	`jnl`	Strongly refuting all semi-random Boolean CSPs. CoRR Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari
2020	—	`conf`	Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. APPROX-RANDOM Sumegha Garg, Pravesh K. Kothari, Ran Raz
2020	J	`jnl`	Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. CoRR Sumegha Garg, Pravesh K. Kothari, Ran Raz
2019	J	`jnl`	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. SIAM J. Comput. Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin
2019	J	`jnl`	List-Decodable Linear Regression. CoRR Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari
2019	J	`jnl`	On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. CoRR Pravesh K. Kothari, Roi Livni
2019	A	`conf`	SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm
2019	A	`conf`	Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS Boaz Barak, Pravesh K. Kothari, David Steurer
2019	—	`conf`	The Social Network Effect on Surprise in Elections. COMAD/CODS Palash Dey, Pravesh K. Kothari, Swaprava Nath
2018	A*	`conf`	An Analysis of the t-SNE Algorithm for Data Visualization. COLT Sanjeev Arora, Wei Hu, Pravesh K. Kothari
2018	J	`jnl`	An Analysis of the t-SNE Algorithm for Data Visualization. CoRR Sanjeev Arora, Wei Hu, Pravesh K. Kothari
2018	J	`jnl`	Communication with Contextual Uncertainty. Comput. Complex. Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan
2018	A*	`conf`	Efficient Algorithms for Outlier-Robust Regression. COLT Adam R. Klivans, Pravesh K. Kothari, Raghu Meka
2018	J	`jnl`	Efficient Algorithms for Outlier-Robust Regression. CoRR Adam R. Klivans, Pravesh K. Kothari, Raghu Meka
2018	A	`conf`	Improper Learning by Refuting. ITCS Pravesh K. Kothari, Roi Livni
2018	—	`conf`	Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). EUROCRYPT (2) Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari
2018	A*	`conf`	Robust moment estimation and improved clustering via sum of squares. STOC Pravesh K. Kothari, Jacob Steinhardt, David Steurer
2018	J	`jnl`	Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR Boaz Barak, Pravesh K. Kothari, David Steurer
2018	J	`jnl`	Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. CoRR Pravesh K. Kothari, Ruta Mehta
2018	A*	`conf`	Sum-of-squares meets nash: lower bounds for finding any equilibrium. STOC Pravesh K. Kothari, Ruta Mehta
2018	J	`jnl`	Surprise in Elections. CoRR Palash Dey, Pravesh K. Kothari, Swaprava Nath
2017	A*	`conf`	Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
2017	J	`jnl`	Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR Pravesh K. Kothari, Jacob Steinhardt
2017	J	`jnl`	Learning by Refuting. CoRR Pravesh K. Kothari, Roi Livni
2017	J	`jnl`	Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). IACR Cryptol. ePrint Arch. Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari
2017	J	`jnl`	Outlier-robust moment-estimation via sum-of-squares. CoRR Pravesh K. Kothari, David Steurer
2017	A*	`conf`	Quantum entanglement, sum of squares, and the log rank conjecture. STOC Boaz Barak, Pravesh K. Kothari, David Steurer
2017	A*	`conf`	Sum of squares lower bounds for refuting any CSP. STOC Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
2017	J	`jnl`	Sum of squares lower bounds for refuting any CSP. CoRR Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
2017	A*	`conf`	The Power of Sum-of-Squares for Detecting Hidden Structures. FOCS Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2017	J	`jnl`	The power of sum-of-squares for detecting hidden structures. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer
2015	A*	`conf`	Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. STOC Pravesh K. Kothari, Raghu Meka
2015	J	`jnl`	SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four. CoRR Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin
2015	A*	`conf`	Sum of Squares Lower Bounds from Pairwise Independence. STOC Boaz Barak, Siu On Chan, Pravesh K. Kothari