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).