On polynomial-time property for a class of randomized quadratures

We study a class of randomized methods that use a special importance sampling for approximating multivariate integrals over the unit cube [0,1]^s. These methods have errors in the randomized setting significantly smaller that the errors of the classical Monte Carlo method for the spaces of functions considered in this paper. In particular, for periodic functions, to enjoy the polynomial-time and/or strongly polynomial-time properties, these methods require less restrictive assumptions on the spaces than the assumptions required by the classical Monte Carlo methods. Recall that polynomial-time property means, roughly, that the errors are bounded from above by a polynomial in s and in 1/n. Here n is the number of function values used. The strong polynomial-time property means that the error is bounded by a polynomial in 1/n independently of s.