Pravesh Kothari

65 papers A* 13A 1B 2Journal 45Unranked 4

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