On the tractability of linear tensor product problems in the worst case

Anargyros Papageorgiou, Iasonas Petras

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

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 languageEnglish (US)
Pages (from-to)415-419
Number of pages5
JournalJournal of Complexity
Volume25
Issue number5
DOIs
StatePublished - Oct 2009

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