87 citations · 305 across the 39 of their papers we have counts for
3 papers · 1 filter
List-Decodable Linear Regression
Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari
We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than fraction of examples. For any $α…
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…
On the Expressive Power of Kernel Methods and the Efficiency of Kernel Learning by Association Schemes
Pravesh K. Kothari, Roi Livni
We study the expressive power of kernel methods and the algorithmic feasibility of multiple kernel learning for a special rich class of kernels. Specifically, we define \emph{Eucli…