2024/09/27 by Josef Dick, Dick, Josef, Takashi Goda +3 · 1 citation
Mathematics · #Algebraic and Geometric Analysis #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Mathematical Analysis and Transform Methods #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.2410.09060
openalex publication_date 2024/09/27 · openalex created_date 2024/10/20 · openalex updated_date 2026/07/28
In this paper, we present some new (in-)tractability results related to the integration problem in subspaces of the Wiener algebra over the d-dimensional unit cube. We show that intractability holds for multivariate integration in the standard Wiener algebra in the deterministic setting, in contrast to polynomial tractability in an unweighted subspace of the Wiener algebra recently shown by Goda (2023). Moreover, we prove that multivariate integration in the subspace of the Wiener algebra introduced by Goda is strongly polynomially tractable if we switch to the randomized setting. We also identify subspaces in which multivariate integration in the deterministic setting are (strongly) polynomially tractable and we compare these results with the bound which can be obtained via Hoeffding's inequality.