An exponential lower bound for integration under uniform derivative bounds
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Kaiwen Jin
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 unit vectors: a projection makes the function vanish at the samples, while its integral stays large and all derivative bounds are preserved.
Claims
Files and sources
- Paper
- AIM @ a153f46, paper/uniform_derivative_integration.pdf ↗
- Posted on GitHub
- 13 October 2026
No verification run is on record for this version.