Publications (20)
Strategyproofing Peer Assessment via Partitioning: The Price in Terms of Evaluators' Expertise
Komal Dhull, Steven Jecmen, Pravesh Kothari +1
Strategic behavior is a fundamental problem in a variety of real-world applications that require some form of peer assessment, such as peer grading of homeworks, grant proposal rev…
Quantum entanglement, sum of squares, and the log rank conjecture
Boaz Barak, Pravesh Kothari, David Steurer
For every , we give an -time algorithm for the vs \emph{Best Separable State (BSS)} problem of distinguishing, given an $n^2\times…
Learning Coverage Functions and Private Release of Marginals
Vitaly Feldman, Pravesh Kothari
We study the problem of approximating and learning coverage functions. A function is a coverage function, if there exists a universe wit…
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh Kothari +2
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint g…
Communication with Contextual Uncertainty
Badih Ghazi, Ilan Komargodski, Pravesh Kothari +1
We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributiona…
Almost Optimal Pseudorandom Generators for Spherical Caps
Pravesh Kothari, Raghu Meka
Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing ps…
Outlier-Robust Clustering of Non-Spherical Mixtures
Ainesh Bakshi, Pravesh Kothari
We give the first outlier-robust efficient algorithm for clustering a mixture of statistically separated d-dimensional Gaussians (k-GMMs). Concretely, our algorithm takes input…
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries
Pravesh Kothari, Divyarthi Mohan, Ariel Schvartzman +2
We consider a revenue-maximizing seller with items facing a single buyer. We introduce the notion of symmetric menu complexity of a mechanism, which counts the number of distin…
Submodular Functions Are Noise Stable
Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari +1
We show that all non-negative submodular functions have high {\em noise-stability}. As a consequence, we obtain a polynomial-time learning algorithm for this class with respect to…
Tight Bounds on Approximation and Learning of Self-Bounding Functions
Vitaly Feldman, Pravesh Kothari, Jan Vondrák
We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube . Informally, a function $f:{0,1}^n…
Agnostic Learning of Disjunctions on Symmetric Distributions
Vitaly Feldman, Pravesh Kothari
We consider the problem of approximating and learning disjunctions (or equivalently, conjunctions) on symmetric distributions over . Symmetric distributions are distribu…
Differentially Private Online Learning
Prateek Jain, Pravesh Kothari, Abhradeep Thakurta
In this paper, we consider the problem of preserving privacy in the online learning setting. We study the problem in the online convex programming (OCP) framework---a popular onlin…
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…
Sum of Squares Lower Bounds from Pairwise Independence
Boaz Barak, Siu On Chan, Pravesh Kothari
We prove that for every and predicate that supports a pairwise independent distribution, there exists an instance of the $\mat…
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Vitaly Feldman, Pravesh Kothari, Jan Vondrak
We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube . Our main result is th…
Provable Submodular Minimization using Wolfe's Algorithm
Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari
Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained S…
Efficient Certificates of Anti-Concentration Beyond Gaussians
Ainesh Bakshi, Pravesh Kothari, Goutham Rajendran +2
A set of high dimensional points in isotropic position is said to be -anti concentrated if for every direction , the fraction of poi…
Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
Ainesh Bakshi, Arpon Basu, Pravesh Kothari +1
We prove that the maximum eigenvalue of the (both signed and unsigned) Laplacian of level Kikuchi graph of any graph with edges is at most . This confirms four rec…
Improved Certificates for Independence Number in Semirandom Hypergraphs
Pravesh Kothari, Anand Louis, Rameesh Paul +1
We study the problem of efficiently certifying upper bounds on independence number of -uniform hypergraphs in semirandom models. This is a notoriously hard problem, with effi…
SOS lower bounds with hard constraints: think global, act local
Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
Many previous Sum-of-Squares (SOS) lower bounds for CSPs had two deficiencies related to global constraints. First, they were not able to support a "cardinality constraint", as in,…