Quasi-polynomial tractability (Q544123)

This paper deals with tractability of multivariate problems. Polynomial tractability means that the solution of a \(d\)-variate problem can be solved to within \(\varepsilon\) with polynomial cost in \(\varepsilon^{-1}\) and \(d\). Unfortunately, many multivariate problems (e.g., all non-trivial unweighted linear tensor product problems) are not polynomially tractable. It is natural to as for the ``smallest'' non-exponential function \(T:[1,\infty)\times[1,\infty)\to [1,\infty)\) for which the unweighted linear tensor product is \(T\)-tractable. I.e. the cost of a multivariate problem is bounded by a multiple of a power of \(T(\varepsilon^{-1},d)\). This paper considers \(T(x,y)=\exp((1+\ln x)(1+\ln y))\), and calls the corresponding \(T\)-tractability the quasi-polynomial tractability. The authors study unweigthed multivariate problems in the worst-case and randomized settings. They show relations between quasi-polynomial tractability in these two settings and for the two classes of algorithms.