115 citations · 816 across the 62 of their papers we have counts for
4 papers · 1 filter
Learning using Local Membership Queries
Pranjal Awasthi, Vitaly Feldman, Varun Kanade
We introduce a new model of membership query (MQ) learning, where the learning algorithm is restricted to query points that are \emph{close} to random examples drawn from the under…
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces
Anindya De, Ilias Diakonikolas, Vitaly Feldman +1
The \emph{Chow parameters} of a Boolean function are its degree-0 and degree-1 Fourier coefficients. It has been known since 1961 (Chow, Tannenba…
Learning DNF Expressions from Fourier Spectrum
Vitaly Feldman
Since its introduction by Valiant in 1984, PAC learning of DNF expressions remains one of the central problems in learning theory. We consider this problem in the setting where the…
Statistical Algorithms and a Lower Bound for Detecting Planted Clique
Vitaly Feldman, Elena Grigorescu, Lev Reyzin +2
We introduce a framework for proving lower bounds on computational problems over distributions against algorithms that can be implemented using access to a statistical query oracle…