TRACTABILITY OF MULTI-PARAMETRIC EULER AND WIENER
INTEGRATED PROCESSES

Mikhail Lifshits

Anargyros Papageorgiou

Henryk Woźniakowski

Abstract: We study average case approximation of Euler and Wiener integrated processes of
variables which are almost surely -times continuously differentiable with respect to the
-th variable and . Let denote the minimal number of continuous
linear functionals which is needed to find an algorithm that uses such functionals and
whose average case error improves the average case error of the zero algorithm by a factor .
Strong polynomial tractability means that there are nonnegative numbers and such
that

We
prove that the Wiener process is much more difficult to approximate than the Euler process.
Namely, strong polynomial tractability holds for the Euler case iff

whereas it holds for the Wiener case iff

Other types of tractability are also studied.

2000 AMS Mathematics Subject Classification: Primary: 65Y20; Secondary: 41A25,
41A63, 60G15, 60G60.

Keywords and phrases: Tractability, Wiener process, Euler process, integrated
processes, linear approximation.