Pravesh K. Kothari
Pravesh K. Kothari
Research Instructor, Princeton University
Verified email at - Homepage
TitleCited byYear
A randomized scheduler with probabilistic guarantees of finding bugs
S Burckhardt, P Kothari, M Musuvathi, S Nagarakatte
ACM Sigplan Notices 45 (3), 167-178, 2010
Differentially private online learning
P Jain, P Kothari, A Thakurta
Conference on Learning Theory, 24.1-24.34, 2012
A nearly tight sum-of-squares lower bound for the planted clique problem
B Barak, SB Hopkins, J Kelner, P Kothari, A Moitra, A Potechin
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS†…, 2016
Submodular functions are noise stable
M Cheraghchi, A Klivans, P Kothari, HK Lee
Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete†…, 2012
Provable submodular minimization using Wolfe's algorithm
D Chakrabarty, P Jain, P Kothari
Advances in Neural Information Processing Systems, 802-809, 2014
Sum of squares lower bounds for refuting any CSP
PK Kothari, R Mori, R O'Donnell, D Witmer
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing†…, 2017
Sum of squares lower bounds from pairwise independence
B Barak, SO Chan, PK Kothari
Proceedings of the forty-seventh annual ACM symposium on Theory of computing†…, 2015
Learning coverage functions and private release of marginals
V Feldman, P Kothari
Conference on Learning Theory, 679-702, 2014
Representation, approximation and learning of submodular functions using low-rank decision trees
V Feldman, P Kothari, J VondrŠk
Conference on Learning Theory, 711-740, 2013
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
PK Kothari, R Meka, P Raghavendra
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing†…, 2017
Constructing hard functions using learning algorithms
A Klivans, P Kothari, IC Oliveira
2013 IEEE Conference on Computational Complexity, 86-97, 2013
On the integrality gap of degree-4 sum of squares for planted clique
SB Hopkins, P Kothari, AH Potechin, P Raghavendra, T Schramm
ACM Transactions on Algorithms (TALG) 14 (3), 28, 2018
Embedding hard learning problems into gaussian space
A Klivans, P Kothari
Approximation, Randomization, and Combinatorial Optimization. Algorithms and†…, 2014
The power of sum-of-squares for detecting hidden structures
SB Hopkins, PK Kothari, A Potechin, P Raghavendra, T Schramm, ...
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS†…, 2017
Efficient algorithms for outlier-robust regression
A Klivans, PK Kothari, R Meka
arXiv preprint arXiv:1803.03241, 2018
Testing surface area
P Kothari, A Nayyeri, R O'Donnell, C Wu
Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete†…, 2014
Learning coverage functions
V Feldman, P Kothari
arXiv preprint arXiv:1304.2079, 2013
Limits on low-degree pseudorandom generators (or: Sum-of-squares meets program obfuscation)
B Barak, Z Brakerski, I Komargodski, PK Kothari
Annual International Conference on the Theory and Applications of†…, 2018
Robust moment estimation and improved clustering via sum of squares
PK Kothari, J Steinhardt, D Steurer
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing†…, 2018
Sos and planted clique: Tight analysis of MPW moments at all degrees and an optimal lower bound at degree four
SB Hopkins, PK Kothari, A Potechin
arXiv preprint arXiv:1507.05230, 2015
The system can't perform the operation now. Try again later.
Articles 1–20