Does integration of uniformly derivative-bounded analytic functions suffer the dimensional curse?
Note: Esra Sengelen Sevim solved this problem first, in “The curse of dimensionality for integration of infinitely differentiable functions”, J. Complexity 97 (2026), 102074, doi:10.1016/j.jco.2026.102074, whose DOI record dates from August 2026: an exponential lower bound for the same class, allowing adaptive point values and nonlinear algorithms. It is a journal article, which the registry cannot link, so it is not recorded here; the record listed is Kaiwen Jin's later, independent proof.
For $d \ge 1$ let $$F_d = \bigl\{f \in C^\infty([0,1]^d) : \|D^\alpha f\|_\infty \le 1 \text{ for every } \alpha \in \mathbb{N}_0^d\bigr\}, \qquad I_d(f) = \int_{[0,1]^d} f(x)\,dx,$$ where $\alpha = 0$ and every mixed derivative are included, with the same bound one at all orders. Let $n(\varepsilon, d)$ be the smallest number of function values with which a deterministic algorithm approximates $I_d(f)$ within absolute error $\varepsilon$ for every $f \in F_d$; the sample points may be chosen adaptively, the reconstruction may be nonlinear, and quadrature weights need not be positive. The class $F_d$ consists of analytic functions. Novak and Woźniakowski proved that uniform approximation on $F_d$ suffers from the curse of dimensionality, and Wojtaszczyk proved that for every fixed number of samples the minimal worst-case integration error on $F_d$ tends to one as $d \to \infty$, so that integration on $F_d$ is not strongly polynomially tractable.
Problem. Does integration on $F_d$ suffer from the curse of dimensionality: are there $\varepsilon_0 \in (0, 1)$, $c > 0$ and $\rho > 1$ such that $$n(\varepsilon_0, d) \ge c \rho^d$$ for infinitely many dimensions $d$?
Source: Krieg and Ullrich (2026), Section 8.1, after Proposition 8.3; earlier, Woźniakowski (2003) conjectured that integration on this class is intractable. Stated in this quantified form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- CA
- Keywords
- AIM Open Applied Problems, curse of dimensionality, information-based complexity, numerical integration
References
@article{krieg2026acta,
author = {Krieg, David and Ullrich, Mario},
title = {Approximation of functions: optimal sampling and complexity},
journal = {Acta Numer.},
volume = {35},
year = {2026},
pages = {273--457},
doi = {10.1017/S0962492925100287},
eprint = {2602.02066},
archivePrefix = {arXiv},
}
@article{wozniakowski2003,
author = {Wo{\'z}niakowski, Henryk},
title = {Open problems for tractability of multivariate integration},
journal = {J. Complexity},
volume = {19},
number = {3},
year = {2003},
pages = {434--444},
doi = {10.1016/S0885-064X(03)00016-5},
}
@article{wojtaszczyk2003,
author = {Wojtaszczyk, Jakub Onufry},
title = {Multivariate integration in {$C^\infty([0,1]^d)$} is not strongly tractable},
journal = {J. Complexity},
volume = {19},
number = {5},
year = {2003},
pages = {638--643},
doi = {10.1016/S0885-064X(03)00069-4},
eprint = {0803.0441},
archivePrefix = {arXiv},
}
@article{novak2009,
author = {Novak, Erich and Wo{\'z}niakowski, Henryk},
title = {Approximation of infinitely differentiable multivariate functions is intractable},
journal = {J. Complexity},
volume = {25},
number = {4},
year = {2009},
pages = {398--404},
doi = {10.1016/j.jco.2008.11.002},
}
@misc{aim-smooth-integration-dimensional-curse,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Does integration of uniformly derivative-bounded analytic functions suffer the dimensional curse?}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/556-smooth-integration-dimensional-curse.md},
note = {Entry 556 at commit a153f46, 2026-10-13},
}
Resolution claims
We consider integration on the unit cube for smooth functions whose every partial derivative, including the function itself, is bounded by one. For every fixed absolute error tolerance $0<\varepsilon<1$, we prove that deterministic integration requires at least $(1-\varepsilon)(\tfrac12+\sin\tfrac12)^{-d}$ function evaluations in dimension $d$. The bound includes adaptive sampling and nonlinear reconstruction. The proof uses quadratic forms of tensor products of …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-16 | Needs verification → Solution claimed | — | Recorded here: AIM @ a153f46, paper/uniform_derivative_integration.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00773, "Does integration of uniformly derivative-bounded analytic functions suffer the dimensional curse?", clopen.solutions.