### Abstract

It has been an open problem to derive a necessary and sufficient condition for a linear tensor product problem to be weakly tractable in the worst case. The complexity of linear tensor product problems in the worst case depends on the eigenvalues {λ_{i}}_{i ∈ N} of a certain operator. It is known that if λ_{1} = 1 and λ_{2} ∈ (0, 1) then λ_{n} = o ((ln n)^{- 2}), as n → ∞, is a necessary condition for a problem to be weakly tractable. We show that this is a sufficient condition as well.

Original language | English (US) |
---|---|

Pages (from-to) | 415-419 |

Number of pages | 5 |

Journal | Journal of Complexity |

Volume | 25 |

Issue number | 5 |

DOIs | |

State | Published - Oct 2009 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics(all)
- Control and Optimization
- Applied Mathematics

### Keywords

- Complexity
- Multivariate problem
- Tractability

## Fingerprint Dive into the research topics of 'On the tractability of linear tensor product problems in the worst case'. Together they form a unique fingerprint.

## Cite this

Papageorgiou, A., & Petras, I. (2009). On the tractability of linear tensor product problems in the worst case.

*Journal of Complexity*,*25*(5), 415-419. https://doi.org/10.1016/j.jco.2009.05.002