Information Complexity of Multivariate Integration and Approximation

Definitions and mathematical statement

Let $d\geq 1$ be an integer, let $D_d\subset{\mathbb{R}}^d$ be a bounded domain, and let $F$ be a class of functions on $D_d$. The permitted information consists of point evaluations $f(x_i)$, with $x_i\in D_d$. The source asks about two target operators: integration, denoted by $\operatorname{INT}$, and approximation of the input function, denoted by $\operatorname{APP}(f)=f$. The integration measure, function range, integrability assumptions, and approximation output space are not specified.

A conditional formulation of the information-complexity question is as follows. Fix a target $S\in\{\operatorname{INT},\operatorname{APP}\}$, an admissible algorithm model $\mathcal M$, and an error criterion $e$. Let $\mathcal A_n(\mathcal M)$ denote the algorithms permitted by that model that use at most $n$ point evaluations, with the meaning of this evaluation bound specified as part of the model. Define \[ n(\varepsilon;S,F,\mathcal M,e) :=\inf\left\{n\in{\mathbb{Z}}_{\geq0}:\exists A\in\mathcal A_n(\mathcal M)\text{ such that }e(A,S;F)\leq\varepsilon\right\}, \qquad \inf\varnothing:=+\infty. \] For $\varepsilon>0$, determine the number of function values needed to achieve error at most $\varepsilon$, for integration or approximation, as a function of the dimension and the specified problem data.

This formula makes the missing parameters explicit; it is a template for the source question, not a uniquely specified complexity problem. The record does not select $F$, a family of domains as $d$ varies, an integration measure or normalization, a norm or other error criterion, absolute versus relative error, or an algorithm model. In particular, whether sampling is adaptive or randomized and whether the guarantee is uniform over $F$, average-case, or probabilistic remain unresolved. No boundary conditions are supplied.

Short English statement

How many sampled values of a function are needed to approximate its integral or the function itself within tolerance $\varepsilon$? The supplied record leaves the function class, integration setup, error criterion, and sampling model unspecified, so it describes a family of information-complexity questions rather than one precise conjecture.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004379$, title: Information Complexity of Multivariate Integration and Approximation; exact source problem code: catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection. No individual proposer is named; the supplied proposed year is 2020.
• Supplied source citation: New Perspectives and Computational Challenges in High Dimensions (2021), Oberwolfach Reports, pp. 377--416, DOI 10.4171/owr/2020/6: https://doi.org/10.4171/owr/2020/6. This same URL is supplied as the source URL and as the literature source labelled "Oberwolfach report." The background attributes the collection to mathematical workshop reports and their open-problem discussions.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that the function class, domain model, and error criterion are insufficiently specified for a definitive answer. This is supplied dated curation, not independently verified; time-sensitive status and cited claims require independent verification.
• The registry labels the statement corrected_verified and describes repairs to notation, typography, omitted definitions, or duplicate clauses while preserving mathematical content. These are supplied editorial assertions, not independent mathematical verification of this draft or of the open-status label.