  We introduce a novel random integration algorithm that boasts both high
convergence order and polynomial tractability for functions characterized by
sparse frequencies or rapidly decaying Fourier coefficients. Specifically, for
integration in periodic isotropic Sobolev space and the isotropic Sobolev space
with compact support, our approach attains a nearly optimal root mean square
error (RMSE) bound. In contrast to previous nearly optimal algorithms, our
method exhibits polynomial tractability, ensuring that the number of samples
does not scale exponentially with increasing dimensions. Our integration
algorithm also enjoys nearly optimal bound for weighted Korobov space.
Furthermore, the algorithm can be applied without the need for prior knowledge
of weights, distinguishing it from the component-by-component algorithm. For
integration in the Wiener algebra, the sample complexity of our algorithm is
independent of the decay rate of Fourier coefficients. The effectiveness of the
integration is confirmed through numerical experiments.
