The definition of \(g_\phi \)  requires evaluating \(f(B)\)  on all \(B \subseteq A\) , which requires \(n^{|A|}\)  calls to the value oracle for \(f\) . In this section, we show that efficiently estimate \(g_\phi \)  using only a polynomial number of value queries to \(f\) . Our sampling procedure is based on the same general ideas described in [1]}, but here we focus on evaluating only the marginals of \(g_\phi \) , which results in a considerably simpler implementation. In particular, our algorithm does not require computation of the coefficients \(m^{(\phi )}_{a,b}\) .
