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

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029550)