115 citations · 816 across the 62 of their papers we have counts for
4 papers · 1 filter
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Vitaly Feldman, Jan Vondrak
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the…
Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy
Maria Florina Balcan, Vitaly Feldman
We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise and are differentially-private. The framework is based o…
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…
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…