Pravesh K. Kothari

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 89

Top Topics

Kernel Learning

Independent Set

Robust Estimation

Top Venues

Publications

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