New averaging technique for approximating weighted integrals

We consider a new averaging technique for studying the complexity of weighted multivariate integration problems. While the standard averaging requires that ∫DK(x,x)ρ(x)dx<∞, our new technique works under a less restrictive condition ∫DK(x,x)ρ(x)dx<∞. It allows us to conclude the existence of algorithms with the worst case errors bounded by O(n−1/2)O(n−1/2) for a wider class of problems than the techniques used so far. It also leads to more refined sufficient conditions for tractability of the multivariate integration problems, as well as a new class of randomized algorithms with errors bounded by O(n−1ln(ln(n))).