Pravesh Kothari

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 37

Top Topics

Peer Assessment

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Pravesh Kothari, Aaron Potechin, Jeff Xu
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. CoRR (2024)
Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran, Madhur Tulsiani, Aravindan Vijayaraghavan
Efficient Certificates of Anti-Concentration Beyond Gaussians. CoRR (2024)
Pravesh Kothari, Peter Manohar
Superpolynomial Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. Electron. Colloquium Comput. Complex. (2024)
Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu
Is Planted Coloring Easier than Planted Clique? COLT (2023)
Pravesh Kothari, Peter Manohar
An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes. Electron. Colloquium Comput. Complex. (2023)
He Jia, Pravesh Kothari, Santosh S. Vempala
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. CoRR (2023)
Andrej Bogdanov, Pravesh Kothari, Alon Rosen
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. IACR Cryptol. ePrint Arch. 2023 (2023)
Andrej Bogdanov, Pravesh Kothari, Alon Rosen
Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method. Electron. Colloquium Comput. Complex. (2023)
Pravesh Kothari, Pasin Manurangsi, Ameya Velingker
Private Robust Estimation by Stabilizing Convex Relaxations. COLT (2022)
Komal Dhull, Steven Jecmen, Pravesh Kothari, Nihar B. Shah
Strategyproofing Peer Assessment via Partitioning: The Price in Terms of Evaluators' Expertise. HCOMP (2022)
Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, Peter Manohar
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation. Electron. Colloquium Comput. Complex. (2022)
Komal Dhull, Steven Jecmen, Pravesh Kothari, Nihar B. Shah
The Price of Strategyproofing Peer Assessment. CoRR (2022)
Ainesh Bakshi, Pravesh Kothari
Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR (2020)
Ainesh Bakshi, Pravesh Kothari
List-Decodable Subspace Recovery via Sum-of-Squares. CoRR (2020)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
approximation and learning of self-bounding functions. Theor. Comput. Sci. 808 (2020)
Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
Playing Unique Games on Certified Small-Set Expanders. CoRR (2020)
Noah Fleming, Pravesh Kothari, Toniann Pitassi
Semialgebraic Proofs and Efficient Algorithm Design. Electron. Colloquium Comput. Complex. 26 (2019)
Noah Fleming, Pravesh Kothari, Toniann Pitassi
Semialgebraic Proofs and Efficient Algorithm Design. Found. Trends Theor. Comput. Sci. 14 (1-2) (2019)
Sushrut Karmalkar, Adam R. Klivans, Pravesh Kothari
List-decodable Linear Regression. NeurIPS (2019)
Pravesh Kothari, Sahil Singla, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. FOCS (2019)
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
Sum-of-Squares Meets Program Obfuscation, Revisited. EUROCRYPT (1) (2019)
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg
Approximation Schemes for a Buyer with Independent Items via Symmetries. CoRR (2019)
Pravesh Kothari, Ruta Mehta
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. Electron. Colloquium Comput. Complex. 25 (2018)
Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai
Sum-of-Squares Meets Program Obfuscation, Revisited. IACR Cryptol. ePrint Arch. 2018 (2018)
Boaz Barak, Pravesh Kothari, David Steurer
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. 25 (2018)
Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
SOS lower bounds with hard constraints: think global, act local. CoRR (2018)
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. ACM Trans. Algorithms 14 (3) (2018)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Approximation and Learning of Self-Bounding Functions. ALT (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. CoRR (2017)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Electron. Colloquium Comput. Complex. 24 (2017)
Boaz Barak, Pravesh Kothari, David Steurer
Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. 24 (2017)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. FOCS (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. CoRR (2016)
Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Electron. Colloquium Comput. Complex. 23 (2016)
Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. SODA (2016)
Pravesh Kothari, Raghu Meka, Prasad Raghavendra
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR (2016)
Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique. SODA (2016)
Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. CoRR (2015)
Boaz Barak, Siu On Chan, Pravesh Kothari
Sum of Squares Lower Bounds from Pairwise Independence. CoRR (2015)
Vitaly Feldman, Pravesh Kothari
Agnostic learning of disjunctions on symmetric distributions. J. Mach. Learn. Res. 16 (2015)
Ilan Komargodski, Pravesh Kothari, Madhu Sudan
Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. 22 (2015)
Adam R. Klivans, Pravesh Kothari
Embedding Hard Learning Problems into Gaussian Space. Electron. Colloquium Comput. Complex. 21 (2014)
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
Provable Submodular Minimization using Wolfe's Algorithm. CoRR (2014)
Pravesh Kothari, Raghu Meka
Almost Optimal Pseudorandom Generators for Spherical Caps. CoRR (2014)
Adam R. Klivans, Pravesh Kothari
Embedding Hard Learning Problems Into Gaussian Space. APPROX-RANDOM (2014)
Vitaly Feldman, Pravesh Kothari
Agnostic Learning of Disjunctions on Symmetric Distributions. CoRR (2014)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Approximation of Self-Bounding Functions. CoRR (2014)
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
Provable Submodular Minimization using Wolfe's Algorithm. NIPS (2014)
Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu
Testing Surface Area. SODA (2014)
Vitaly Feldman, Pravesh Kothari
Learning Coverage Functions and Private Release of Marginals. COLT (2014)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees CoRR (2013)
Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira
Constructing Hard Functions Using Learning Algorithms. Computational Complexity Conference (2013)
Vitaly Feldman, Pravesh Kothari
Learning Coverage Functions CoRR (2013)
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. COLT (2013)
Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira
Constructing Hard Functions from Learning Algorithms. Electron. Colloquium Comput. Complex. 20 (2013)
Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari
An Explicit VC-Theorem for Low-Degree Polynomials. APPROX-RANDOM (2012)
Prateek Jain, Pravesh Kothari, Abhradeep Thakurta
Differentially Private Online Learning. COLT (2012)
Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari
An Explicit VC-Theorem for Low-Degree Polynomials. Electron. Colloquium Comput. Complex. 19 (2012)
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
Submodular functions are noise stable. SODA (2012)
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
Submodular Functions Are Noise Stable. Electron. Colloquium Comput. Complex. 18 (2011)
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee
Submodular Functions Are Noise Stable CoRR (2011)
Prateek Jain, Pravesh Kothari, Abhradeep Thakurta
Differentially Private Online Learning CoRR (2011)
Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, Santosh Nagarakatte
A randomized scheduler with probabilistic guarantees of finding bugs. ASPLOS (2010)