Before revision:  sets from \mathcal{S . Such a polynomial is called a " generalized partitioning polynomial " . We present a randomized algorithm that efficiently computes such a polynomial P. Specifically, the expected running time of our algorithm is only linear in | \mathcal{S | , where the constant of proportionality depends on d, D, and the complexity of the description of~\mathcal{S . Our approach exploits the technique of "quantifier elimination " combined with that of " \epsilon-samples ".
After revision:  sets from \mathcal{S . Such a polynomial is called a " generalized partitioning polynomial " . We present a randomized algorithm that computes such polynomials efficiently -- the expected running time of our algorithm is only linear in | \mathcal{S | , where the constant of proportionality depends on d, D, and the complexity of the description of~\mathcal{S . Our approach exploits the technique of "quantifier elimination " combined with that of " \epsilon-samples ".