## Abstract

We study EC-(s,t)-weak tractability of multivariate linear problems in the average case setting. This paper extends earlier work in the worst case setting. The parameters s≥0 and t≥0 allow us to study the information complexity n(ε,d) of a d-variate problem with respect to different powers of lnε^{−1}, corresponding to the bits of accuracy, and d. We consider the absolute and normalized error criteria. In particular, a multivariate problem is EC-(s,t)-weakly tractable iff lim_{d+ε−1→∞}lnn(ε,d)∕[d^{t}+ln^{s}ε^{−1}]=0. We deal with general linear problems and linear tensor product problems. We show necessary and sufficient conditions for EC-(s,t)-weak tractability. In the case of general linear problem these conditions are matching. For linear tensor product problems, we also show matching conditions with the exception of some cases where s>1, in general.

Original language | English (US) |
---|---|

Article number | 101425 |

Journal | Journal of Complexity |

Volume | 55 |

DOIs | |

State | Published - Dec 2019 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics

## Keywords

- Average case setting
- EC-(s,t)-weak tractability
- Hilbert space
- Linear problem
- Linear tensor product problem