FoCM 2014 conference
Workshop B5 - Information Based Complexity
December 15, 17:00 ~ 17:30 - Room B23
Tractability of the Approximation of High-Dimensional Rank One Tensors
Erich Novak
Jena University , Germany - erich.novak@uni-jena.de
We study the approximation of high-dimensional rank one tensors using point evaluations. We prove that for certain parameters (smoothness and norm of the $r$th derivative) this problem is intractable while for other parameters the problem is tractable and the complexity is only polynomial in the dimension. We completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the ``difficult'' case we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.
Joint work with Daniel Rudolf (Jena University, Germany).