Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting (Q1029550)

Let a \(d\)-variate (multivariate) linear problem be given, where \(d\) is arbitrary. Such a problem will be studied in the average (zero) case setting, i.e. with respect to a Gaussian measure with zero-mean. The situation considered includes the aforementioned \(d\)-variate functions which, in turn, are sums of \(q^*\)-variate functions. The influcence of these functions may be weighted by weights of finite order. Here, in contrast to the arbitrary \(d\), \(q^*\) shall remain fixed. The purpose of the paper is to solve these problems in a constructive way by algorithms that have polynomial time. Given a positive \(\varepsilon\), the problems are, however, only solved up to an error of size \(\varepsilon\). Since the algorithms are at most of polynomial time they use \(\varepsilon^{-p}d^{q^*}\) function evaluations, where \(\varepsilon\) is as prescribed before and \(p\) is a measurement for the difficulty of the univariate problem. Here, powers of \(\log\varepsilon\) are ignored. The central fact about the complexity of the algorithm is stated in Theorem~2 of the paper. Following the theorem, there are examples of such problem which are solved by the algorithms using integration or approximation of functions.