Learning sparse Boolean polynomials

We are given a Boolean function f : {-1,1} n → R that can be written as a sparse linear combination of s polynomials. The Junta problem cf. [1] is an instance of such a setting. Our goal is to learn the function f by accessing its values at randomly sampled m elements from {-1, l} n . In this paper,... View More