FoCM 2014 conference
Workshop B5 - Information Based Complexity
December 17, 16:00 ~ 16:30 - Room B23
Linear Tensor Product Problems and New Notions of Tractability
Pawel Siedlecki
University of Warsaw, Poland - psiedlecki@mimuw.edu.pl
We study the information complexity $n(\varepsilon,d)$ of linear tensor product problems in the worst and average case settings in terms of two recently introduced notions of tractability: uniform weak tractability and $(s,t)$-weak tractability. Here, $d$ denotes the number of variables and $\varepsilon$ is an error threshold. Uniform weak tractability means that the information complexity $n(\varepsilon,d)$ is not an exponential function of any positive power of $\varepsilon^{-1}$ and/or $d$, whereas $(s,t)$-weak tractability means that the information complexity $n(\varepsilon,d)$ is not an exponential function of $\varepsilon^{-s}$ and/or $d^{\,t}$. These notions allow us to refine tractability hierarchy of multivariate problems. We give necessary and sufficient conditions on these notions of tractability for homogeneous linear tensor product problems. This is also done for some nonhomogeneous linear tensor product problems in terms of their intrinsic nonhomogeneity parameters such as their regularity with respect to succesive variables or weights associated to variables and groups of variables. The work on $(s,t)$-weak tractability has been jointly done with Markus Weimar.