
Pravesh Kothari
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2020
- [j6]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Tight bounds on ℓ1 approximation and learning of self-bounding functions. Theor. Comput. Sci. 808: 86-98 (2020) - [c34]Pravesh K. Kothari, Roi Livni:
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. ALT 2020: 422-450 - [c33]Sumegha Garg, Pravesh K. Kothari, Ran Raz:
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. APPROX/RANDOM 2020: 21:1-21:18 - [i48]Ainesh Bakshi, Pravesh Kothari:
List-Decodable Subspace Recovery via Sum-of-Squares. CoRR abs/2002.05139 (2020) - [i47]Sumegha Garg, Pravesh K. Kothari, Ran Raz:
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG. CoRR abs/2002.07235 (2020) - [i46]Ainesh Bakshi, Pravesh Kothari:
Outlier-Robust Clustering of Non-Spherical Mixtures. CoRR abs/2005.02970 (2020) - [i45]Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer:
Playing Unique Games on Certified Small-Set Expanders. CoRR abs/2006.09969 (2020) - [i44]Jackson Abascal, Venkatesan Guruswami, Pravesh K. Kothari:
Strongly refuting all semi-random Boolean CSPs. CoRR abs/2009.08032 (2020) - [i43]Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer:
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. CoRR abs/2011.06585 (2020) - [i42]Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala:
Robustly Learning Mixtures of k Arbitrary Gaussians. CoRR abs/2012.02119 (2020)
2010 – 2019
- 2019
- [j5]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Found. Trends Theor. Comput. Sci. 14(1-2): 1-221 (2019) - [j4]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): 687-735 (2019) - [c32]Palash Dey, Pravesh K. Kothari, Swaprava Nath:
The Social Network Effect on Surprise in Elections. COMAD/CODS 2019: 1-9 - [c31]Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai:
Sum-of-Squares Meets Program Obfuscation, Revisited. EUROCRYPT (1) 2019: 226-250 - [c30]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: 220-232 - [c29]Boaz Barak, Pravesh K. Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. ITCS 2019: 9:1-9:12 - [c28]Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm:
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS 2019: 49:1-49:21 - [c27]Sushrut Karmalkar, Adam R. Klivans, Pravesh Kothari:
List-decodable Linear Regression. NeurIPS 2019: 7423-7432 - [i41]Pravesh K. Kothari, Roi Livni:
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes. CoRR abs/1902.04782 (2019) - [i40]Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman, Sahil Singla, S. Matthew Weinberg:
Approximation Schemes for a Buyer with Independent Items via Symmetries. CoRR abs/1905.05231 (2019) - [i39]Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari:
List-Decodable Linear Regression. CoRR abs/1905.05679 (2019) - [i38]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Electron. Colloquium Comput. Complex. 26: 106 (2019) - 2018
- [j3]Badih Ghazi, Ilan Komargodski, Pravesh K. Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Comput. Complex. 27(3): 463-509 (2018) - [j2]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): 28:1-28:31 (2018) - [c26]Adam R. Klivans, Pravesh K. Kothari, Raghu Meka:
Efficient Algorithms for Outlier-Robust Regression. COLT 2018: 1420-1430 - [c25]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. COLT 2018: 1455-1462 - [c24]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: 649-679 - [c23]Pravesh K. Kothari, Roi Livni:
Improper Learning by Refuting. ITCS 2018: 55:1-55:10 - [c22]Pravesh K. Kothari, Jacob Steinhardt, David Steurer:
Robust moment estimation and improved clustering via sum of squares. STOC 2018: 1035-1046 - [c21]Pravesh K. Kothari, Ruta Mehta:
Sum-of-squares meets nash: lower bounds for finding any equilibrium. STOC 2018: 1241-1248 - [i37]Palash Dey, Pravesh K. Kothari, Swaprava Nath
:
Surprise in Elections. CoRR abs/1801.10110 (2018) - [i36]Sanjeev Arora, Wei Hu, Pravesh K. Kothari:
An Analysis of the t-SNE Algorithm for Data Visualization. CoRR abs/1803.01768 (2018) - [i35]Adam R. Klivans, Pravesh K. Kothari, Raghu Meka:
Efficient Algorithms for Outlier-Robust Regression. CoRR abs/1803.03241 (2018) - [i34]Boaz Barak, Pravesh K. Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. CoRR abs/1804.08662 (2018) - [i33]Pravesh K. Kothari, Ruta Mehta:
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. CoRR abs/1806.09426 (2018) - [i32]Pravesh Kothari, Ryan O'Donnell, Tselil Schramm:
SOS lower bounds with hard constraints: think global, act local. CoRR abs/1809.01207 (2018) - [i31]Boaz Barak, Pravesh Kothari, David Steurer:
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Electron. Colloquium Comput. Complex. 25: 77 (2018) - [i30]Pravesh Kothari, Ruta Mehta:
Sum-of-Squares meets Nash: Optimal Lower Bounds for Finding any Equilibrium. Electron. Colloquium Comput. Complex. 25: 126 (2018) - [i29]Boaz Barak, Samuel B. Hopkins, Aayush Jain, Pravesh Kothari, Amit Sahai:
Sum-of-Squares Meets Program Obfuscation, Revisited. IACR Cryptol. ePrint Arch. 2018: 1237 (2018) - 2017
- [c20]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Tight Bounds on ℓ1 Approximation and Learning of Self-Bounding Functions. ALT 2017: 540-559 - [c19]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: 720-731 - [c18]Pravesh K. Kothari, Ryuhei Mori
, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. STOC 2017: 132-145 - [c17]Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra:
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC 2017: 590-603 - [c16]Boaz Barak, Pravesh K. Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. STOC 2017: 975-988 - [i28]Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer:
Sum of squares lower bounds for refuting any CSP. CoRR abs/1701.04521 (2017) - [i27]Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. CoRR abs/1701.06321 (2017) - [i26]Pravesh K. Kothari, Roi Livni:
Learning by Refuting. CoRR abs/1709.03871 (2017) - [i25]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 abs/1710.05017 (2017) - [i24]Pravesh K. Kothari, Jacob Steinhardt:
Better Agnostic Clustering Via Relaxed Tensor Norms. CoRR abs/1711.07465 (2017) - [i23]Pravesh K. Kothari, David Steurer:
Outlier-robust moment-estimation via sum-of-squares. CoRR abs/1711.11581 (2017) - [i22]Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. Electron. Colloquium Comput. Complex. 24: 11 (2017) - [i21]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: 60 (2017) - [i20]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: 312 (2017) - 2016
- [c15]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: 428-437 - [c14]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: 1079-1095 - [c13]Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. SODA 2016: 2072-2085 - [i19]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 abs/1604.03084 (2016) - [i18]Pravesh Kothari, Raghu Meka, Prasad Raghavendra:
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR abs/1610.02704 (2016) - [i17]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: 58 (2016) - 2015
- [j1]Vitaly Feldman, Pravesh Kothari:
Agnostic learning of disjunctions on symmetric distributions. J. Mach. Learn. Res. 16: 3455-3467 (2015) - [c12]Boaz Barak, Siu On Chan, Pravesh K. Kothari:
Sum of Squares Lower Bounds from Pairwise Independence. STOC 2015: 97-106 - [c11]Pravesh K. Kothari, Raghu Meka:
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. STOC 2015: 247-256 - [i16]Boaz Barak, Siu On Chan, Pravesh Kothari:
Sum of Squares Lower Bounds from Pairwise Independence. CoRR abs/1501.00734 (2015) - [i15]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. CoRR abs/1504.04813 (2015) - [i14]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 abs/1507.05230 (2015) - [i13]Ilan Komargodski, Pravesh Kothari, Madhu Sudan:
Communication with Contextual Uncertainty. Electron. Colloquium Comput. Complex. 22: 64 (2015) - 2014
- [c10]Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems Into Gaussian Space. APPROX-RANDOM 2014: 793-809 - [c9]Vitaly Feldman, Pravesh Kothari:
Learning Coverage Functions and Private Release of Marginals. COLT 2014: 679-702 - [c8]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. NIPS 2014: 802-809 - [c7]Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu:
Testing Surface Area. SODA 2014: 1204-1214 - [i12]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Nearly Tight Bounds on ℓ1 Approximation of Self-Bounding Functions. CoRR abs/1404.4702 (2014) - [i11]Vitaly Feldman, Pravesh Kothari:
Agnostic Learning of Disjunctions on Symmetric Distributions. CoRR abs/1405.6791 (2014) - [i10]Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari:
Provable Submodular Minimization using Wolfe's Algorithm. CoRR abs/1411.0095 (2014) - [i9]Pravesh Kothari, Raghu Meka:
Almost Optimal Pseudorandom Generators for Spherical Caps. CoRR abs/1411.6299 (2014) - [i8]Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems into Gaussian Space. Electron. Colloquium Comput. Complex. 21: 63 (2014) - 2013
- [c6]Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira:
Constructing Hard Functions Using Learning Algorithms. Computational Complexity Conference 2013: 86-97 - [c5]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. COLT 2013: 711-740 - [i7]Vitaly Feldman, Pravesh Kothari, Jan Vondrák:
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees. CoRR abs/1304.0730 (2013) - [i6]Vitaly Feldman, Pravesh Kothari:
Learning Coverage Functions. CoRR abs/1304.2079 (2013) - [i5]Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira:
Constructing Hard Functions from Learning Algorithms. Electron. Colloquium Comput. Complex. 20: 129 (2013) - 2012
- [c4]Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. APPROX-RANDOM 2012: 495-504 - [c3]Mahdi Cheraghchi
, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular functions are noise stable. SODA 2012: 1586-1592 - [c2]Prateek Jain, Pravesh Kothari, Abhradeep Thakurta:
Differentially Private Online Learning. COLT 2012: 24.1-24.34 - [i4]Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. Electron. Colloquium Comput. Complex. 19: 127 (2012) - 2011
- [i3]Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable. CoRR abs/1106.0518 (2011) - [i2]Prateek Jain, Pravesh Kothari, Abhradeep Thakurta:
Differentially Private Online Learning. CoRR abs/1109.0105 (2011) - [i1]Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin K. Lee:
Submodular Functions Are Noise Stable. Electron. Colloquium Comput. Complex. 18: 90 (2011) - 2010
- [c1]Sebastian Burckhardt, Pravesh Kothari, Madanlal Musuvathi, Santosh Nagarakatte
:
A randomized scheduler with probabilistic guarantees of finding bugs. ASPLOS 2010: 167-178
Coauthor Index

manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
load content from web.archive.org
Privacy notice: By enabling the option above, your browser will contact the API of web.archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
Tweets on dblp homepage
Show tweets from on the dblp homepage.
Privacy notice: By enabling the option above, your browser will contact twitter.com and twimg.com to load tweets curated by our Twitter account. At the same time, Twitter will persistently store several cookies with your web browser. While we did signal Twitter to not track our users by setting the "dnt" flag, we do not have any control over how Twitter uses your data. So please proceed with care and consider checking the Twitter privacy policy.
last updated on 2020-12-05 23:01 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint