In this talk, I will describe a learning algorithm that learns the target function by finding a sparse function. The main advantage of the algorithm is that its running time is polynomial in the number of non-zero coefficients. However, the disadvantage is that the algorithm uses the query model.
I will first show that, if function f can be approximated by a polynomial sparse function g, then it can be approximated by a polynomial sparse function that has only "significant" coefficients. Then I will show a randomized polynomial time procedure that given a function f and a threshold \theta outputs (w.p. 1-\delta) all the coefficients for which |^f(z)|>=\theta. And the procedure runs in polynomial time in n, 1/\theta and \log(1/\delta).