On polynomial-time property for a class of randomized quadratures

Greg W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


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.

Original languageEnglish
Pages (from-to)624-637
Number of pages14
JournalJournal of Complexity
Issue number5
StatePublished - Oct 2004

Bibliographical note

Funding Information:
$The author was partially supported by the National Science Foundation under Grant CCR-0095709. E-mail address: [email protected].


  • Importance sampling
  • Monte Carlo methods
  • Multivariate integration
  • Randomized methods
  • Tractability

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'On polynomial-time property for a class of randomized quadratures'. Together they form a unique fingerprint.

Cite this