115 citations · 816 across the 62 of their papers we have counts for
4 papers · 1 filter
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…
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…
Agnostic Learning of Monomials by Halfspaces is Hard
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra +1
We prove the following strong hardness result for learning: Given a distribution of labeled examples from the hypercube such that there exists a monomial consistent with $(1-\eps)$…
A Complete Characterization of Statistical Query Learning with Applications to Evolvability
Vitaly Feldman
Statistical query (SQ) learning model of Kearns (1993) is a natural restriction of the PAC learning model in which a learning algorithm is allowed to obtain estimates of statistica…