87 citations · 305 across the 39 of their papers we have counts for
4 papers · 1 filter
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…
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…
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…
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…