A randomized scheduler with probabilistic guarantees of finding bugs. - Sebastian Burckhardt; Pravesh Kothari; Madanlal Musuvathi; Santosh Nagarakatte (ASPLOS, 2010)

An Explicit VC-Theorem for Low-Degree Polynomials. - Eshan Chattopadhyay; Adam R. Klivans; Pravesh Kothari (APPROX-RANDOM, 2012)

Submodular functions are noise stable. - Mahdi Cheraghchi; Adam R. Klivans; Pravesh Kothari; Homin K. Lee (SODA, 2012)

Differentially Private Online Learning. - Prateek Jain 002; Pravesh Kothari; Abhradeep Thakurta (COLT, 2012)

Constructing Hard Functions Using Learning Algorithms. - Adam R. Klivans; Pravesh Kothari; Igor C. Oliveira 001 (CCC, 2013)

Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. - Vitaly Feldman; Pravesh Kothari; Jan Vondrák (COLT, 2013)

Learning Coverage Functions - Vitaly Feldman; Pravesh Kothari (CoRR, 2013)

Constructing Hard Functions from Learning Algorithms. - Adam R. Klivans; Pravesh Kothari; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2013)

Embedding Hard Learning Problems Into Gaussian Space. - Adam R. Klivans; Pravesh Kothari (APPROX-RANDOM, 2014)

Learning Coverage Functions and Private Release of Marginals. - Vitaly Feldman; Pravesh Kothari (COLT, 2014)

Provable Submodular Minimization using Wolfe's Algorithm. - Deeparnab Chakrabarty; Prateek Jain 002; Pravesh Kothari (NIPS, 2014)

Testing Surface Area. - Pravesh Kothari; Amir Nayyeri; Ryan O'Donnell; Chenggang Wu 003 (SODA, 2014)

Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions. - Vitaly Feldman; Pravesh Kothari; Jan Vondrák (CoRR, 2014)

Almost Optimal Pseudorandom Generators for Spherical Caps. - Pravesh Kothari; Raghu Meka (CoRR, 2014)

Sum of Squares Lower Bounds from Pairwise Independence. - Boaz Barak; Siu On Chan; Pravesh K. Kothari (STOC, 2015)

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. - Pravesh K. Kothari; Raghu Meka (STOC, 2015)

SoS and Planted Clique: Tight Analysis of MPW Moments at all Degrees and an Optimal Lower Bound at Degree Four. - Samuel B. Hopkins 001; Pravesh K. Kothari; Aaron Potechin (CoRR, 2015)

Communication with Contextual Uncertainty. - Ilan Komargodski; Pravesh Kothari; Madhu Sudan 001 (Electron. Colloquium Comput. Complex., 2015)

Agnostic learning of disjunctions on symmetric distributions. - Vitaly Feldman; Pravesh Kothari (J. Mach. Learn. Res., 2015)

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. - Boaz Barak; Samuel B. Hopkins 001; Jonathan A. Kelner; Pravesh Kothari; Ankur Moitra; Aaron Potechin (FOCS, 2016)

Communication with Contextual Uncertainty. - Badih Ghazi; Ilan Komargodski; Pravesh Kothari; Madhu Sudan 001 (SODA, 2016)

On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. - Samuel B. Hopkins 001; Pravesh Kothari; Aaron Henry Potechin; Prasad Raghavendra; Tselil Schramm (SODA, 2016)

Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions. - Vitaly Feldman; Pravesh Kothari; Jan Vondrák (ALT, 2017)

The Power of Sum-of-Squares for Detecting Hidden Structures. - Samuel B. Hopkins 001; Pravesh K. Kothari; Aaron Potechin; Prasad Raghavendra; Tselil Schramm; David Steurer (FOCS, 2017)

Quantum entanglement, sum of squares, and the log rank conjecture. - Boaz Barak; Pravesh K. Kothari; David Steurer (STOC, 2017)

Sum of squares lower bounds for refuting any CSP. - Pravesh K. Kothari; Ryuhei Mori; Ryan O'Donnell; David Witmer (STOC, 2017)

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. - Pravesh K. Kothari; Raghu Meka; Prasad Raghavendra (STOC, 2017)

Learning by Refuting. - Pravesh K. Kothari; Roi Livni (CoRR, 2017)

Better Agnostic Clustering Via Relaxed Tensor Norms. - Pravesh K. Kothari; Jacob Steinhardt (CoRR, 2017)

Outlier-robust moment-estimation via sum-of-squares. - Pravesh K. Kothari; David Steurer (CoRR, 2017)

An Analysis of the t-SNE Algorithm for Data Visualization. - Sanjeev Arora; Wei Hu 014; Pravesh K. Kothari (COLT, 2018)

Efficient Algorithms for Outlier-Robust Regression. - Adam R. Klivans; Pravesh K. Kothari; Raghu Meka (COLT, 2018)

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). - Boaz Barak; Zvika Brakerski; Ilan Komargodski; Pravesh K. Kothari (EUROCRYPT (2), 2018)

Improper Learning by Refuting. - Pravesh K. Kothari; Roi Livni (ITCS, 2018)

Sum-of-squares meets nash: lower bounds for finding any equilibrium. - Pravesh K. Kothari; Ruta Mehta (STOC, 2018)

Robust moment estimation and improved clustering via sum of squares. - Pravesh K. Kothari; Jacob Steinhardt; David Steurer (STOC, 2018)

Surprise in Elections. - Palash Dey; Pravesh K. Kothari; Swaprava Nath (CoRR, 2018)

Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. - Pravesh Kothari; Ruta Mehta (Electron. Colloquium Comput. Complex., 2018)

The Social Network Effect on Surprise in Elections. - Palash Dey; Pravesh K. Kothari; Swaprava Nath (COMAD/CODS, 2019)

Sum-of-Squares Meets Program Obfuscation, Revisited. - Boaz Barak; Samuel B. Hopkins 001; Aayush Jain; Pravesh Kothari; Amit Sahai (EUROCRYPT (1), 2019)

Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. - Pravesh Kothari; Sahil Singla 001; Divyarthi Mohan; Ariel Schvartzman; S. Matthew Weinberg (FOCS, 2019)

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. - Boaz Barak; Pravesh K. Kothari; David Steurer (ITCS, 2019)

SOS Lower Bounds with Hard Constraints: Think Global, Act Local. - Pravesh K. Kothari; Ryan O'Donnell; Tselil Schramm (ITCS, 2019)

List-decodable Linear Regression. - Sushrut Karmalkar; Adam R. Klivans; Pravesh Kothari (NeurIPS, 2019)

Approximation Schemes for a Buyer with Independent Items via Symmetries. - Pravesh Kothari; Divyarthi Mohan; Ariel Schvartzman; Sahil Singla 001; S. Matthew Weinberg (CoRR, 2019)

Semialgebraic Proofs and Efficient Algorithm Design. - Noah Fleming; Pravesh Kothari; Toniann Pitassi (Found. Trends Theor. Comput. Sci., 2019)

On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. - Pravesh K. Kothari; Roi Livni (ALT, 2020)

Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. - Sumegha Garg; Pravesh K. Kothari; Ran Raz (APPROX-RANDOM, 2020)

Outlier-Robust Clustering of Gaussians and Other Non-Spherical Mixtures. - Ainesh Bakshi; Ilias Diakonikolas; Samuel B. Hopkins 001; Daniel Kane 001; Sushrut Karmalkar; Pravesh K. Kothari (FOCS, 2020)

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. - Tommaso d'Orsi; Pravesh K. Kothari; Gleb Novikov; David Steurer (FOCS, 2020)

List-Decodable Subspace Recovery via Sum-of-Squares. - Ainesh Bakshi; Pravesh Kothari (CoRR, 2020)

Outlier-Robust Clustering of Non-Spherical Mixtures. - Ainesh Bakshi; Pravesh Kothari (CoRR, 2020)

Robustly Learning Mixtures of k Arbitrary Gaussians. - Ainesh Bakshi; Ilias Diakonikolas; He Jia; Daniel M. Kane; Pravesh K. Kothari; Santosh S. Vempala (CoRR, 2020)

Tight bounds on ℓ1 approximation and learning of self-bounding functions. - Vitaly Feldman; Pravesh Kothari; Jan Vondrák (Theor. Comput. Sci., 2020)

Memory-Sample Lower Bounds for Learning Parity with Noise. - Sumegha Garg; Pravesh K. Kothari; Pengda Liu; Ran Raz (APPROX-RANDOM, 2021)

A Stress-Free Sum-Of-Squares Lower Bound for Coloring. - Pravesh K. Kothari; Peter Manohar (CCC, 2021)

Strongly refuting all semi-random Boolean CSPs. - Jackson Abascal; Venkatesan Guruswami; Pravesh K. Kothari (SODA, 2021)

List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time. - Ainesh Bakshi; Pravesh K. Kothari (SODA, 2021)

Playing unique games on certified small-set expanders. - Mitali Bafna; Boaz Barak; Pravesh K. Kothari; Tselil Schramm; David Steurer (STOC, 2021)

Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally. - Pravesh K. Kothari; Peter Manohar; Brian Hu Zhang (ALT, 2022)

Bypassing the XOR Trick: Stronger Certificates for Hypergraph Clique Number. - Venkatesan Guruswami; Pravesh K. Kothari; Peter Manohar (APPROX/RANDOM, 2022)

Private Robust Estimation by Stabilizing Convex Relaxations. - Pravesh Kothari; Pasin Manurangsi; Ameya Velingker (COLT, 2022)

Polynomial-Time Power-Sum Decomposition of Polynomials. - Mitali Bafna; Jun-Ting Hsieh; Pravesh K. Kothari; Jeff Xu (FOCS, 2022)

Strategyproofing Peer Assessment via Partitioning: The Price in Terms of Evaluators' Expertise. - Komal Dhull; Steven Jecmen; Pravesh Kothari; Nihar B. Shah (HCOMP, 2022)

Algorithmic Thresholds for Refuting Random Polynomial Systems. - Jun-Ting Hsieh; Pravesh K. Kothari (SODA, 2022)

Robustly learning mixtures of k arbitrary Gaussians. - Ainesh Bakshi; Ilias Diakonikolas; He Jia; Daniel M. Kane; Pravesh K. Kothari; Santosh S. Vempala (STOC, 2022)

Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random. - Venkatesan Guruswami; Pravesh K. Kothari; Peter Manohar (STOC, 2022)

List-decodable covariance estimation. - Misha Ivkov; Pravesh K. Kothari (STOC, 2022)

The Price of Strategyproofing Peer Assessment. - Komal Dhull; Steven Jecmen; Pravesh Kothari; Nihar B. Shah (CoRR, 2022)

Is Planted Coloring Easier than Planted Clique? - Pravesh Kothari; Santosh S. Vempala; Alexander S. Wein; Jeff Xu (COLT, 2023)

Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. - Venkatesan Guruswami; Jun-Ting Hsieh; Pravesh K. Kothari; Peter Manohar (FOCS, 2023)

Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. - He Jia; Pravesh K. Kothari; Santosh S. Vempala (FOCS, 2023)

Approximating Max-Cut on Bounded Degree Graphs: Tighter Analysis of the FKL Algorithm. - Jun-Ting Hsieh; Pravesh K. Kothari (ICALP, 2023)

Ellipsoid Fitting up to a Constant. - Jun-Ting Hsieh; Pravesh K. Kothari; Aaron Potechin; Jeff Xu (ICALP, 2023)

A simple and sharper proof of the hypergraph Moore bound. - Jun-Ting Hsieh; Pravesh K. Kothari; Sidhanth Mohanty (SODA, 2023)

Privately Estimating a Gaussian: Efficient, Robust, and Optimal. - Daniel Alabi; Pravesh K. Kothari; Pranay Tankala; Prayaag Venkat; Fred Zhang (STOC, 2023)

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. - Omar Alrabiah; Venkatesan Guruswami; Pravesh K. Kothari; Peter Manohar (STOC, 2023)

Algorithms Approaching the Threshold for Semi-random Planted Clique. - Rares-Darius Buhai; Pravesh K. Kothari; David Steurer (STOC, 2023)

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. - Aravind Gollakota; Adam R. Klivans; Pravesh K. Kothari (STOC, 2023)

Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. - Andrej Bogdanov; Pravesh K. Kothari; Alon Rosen (TCC (1), 2023)

Efficient Certificates of Anti-Concentration Beyond Gaussians. - Ainesh Bakshi; Pravesh K. Kothari; Goutham Rajendran; Madhur Tulsiani; Aravindan Vijayaraghavan (FOCS, 2024)

Semirandom Planted Clique and the Restricted Isometry Property. - Jaroslaw Blasiok; Rares-Darius Buhai; Pravesh K. Kothari; David Steurer (FOCS, 2024)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. - Pravesh K. Kothari; Peter Manohar (FOCS, 2024)

New SDP Roundings and Certifiable Approximation for Cubic Optimization. - Jun-Ting Hsieh; Pravesh K. Kothari; Lucas Pesenti; Luca Trevisan 001 (SODA, 2024)

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. - Pravesh K. Kothari; Peter Manohar (STOC, 2024)

Sum-of-Squares Lower Bounds for Independent Set on Ultra-Sparse Random Graphs. - Pravesh K. Kothari; Aaron Potechin; Jeff Xu (STOC, 2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs. - Jun-Ting Hsieh; Pravesh K. Kothari; Sidhanth Mohanty; David Munhá Correia; Benny Sudakov (CoRR, 2024)

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 (CoRR, 2024)

Overcomplete Tensor Decomposition via Koszul-Young Flattenings. - Pravesh K. Kothari; Ankur Moitra; Alexander S. Wein (CoRR, 2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes. - Arpon Basu; Jun-Ting Hsieh; Pravesh Kothari; Andrew D. Lin (Electron. Colloquium Comput. Complex., 2024)

Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. - Pravesh Kothari; Peter Manohar (Electron. Colloquium Comput. Complex., 2024)

Rounding Large Independent Sets on Expanders. - Mitali Bafna; Jun-Ting Hsieh; Pravesh K. Kothari (STOC, 2025)

Sum-Of-Squares To Approximate Knapsack. - Pravesh K. Kothari; Sherry Sarkar (CoRR, 2025)

New Spectral Algorithms for Refuting Smoothed k-SAT. - Venkatesan Guruswami; Pravesh K. Kothari; Peter Manohar (Commun. ACM, 2025)

The Quasi-Polynomial Low-Degree Conjecture is False. - Rares-Darius Buhai; Jun-Ting Hsieh; Aayush Jain; Pravesh K. Kothari (CoRR, 2025)

Sparsifying Sums of Positive Semidefinite Matrices. - Arpon Basu; Pravesh K. Kothari; Yang P. Liu; Raghu Meka (CoRR, 2025)

Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices. - Pravesh K. Kothari; Jeff Xu (CoRR, 2025)