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

Anargyros Papageorgiou; Iasonas Petras

doi:10.1016/j.jco.2009.05.002

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

Anargyros Papageorgiou, Iasonas Petras

Research output: Contribution to journal › Article › peer-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 and λ₂ ∈ (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	https://doi.org/10.1016/j.jco.2009.05.002
State	Published - Oct 2009
Externally published	Yes

All Science Journal Classification (ASJC) codes

Algebra and Number Theory
Statistics and Probability
Numerical Analysis
General Mathematics
Control and Optimization
Applied Mathematics

Keywords

Complexity
Multivariate problem
Tractability

Access to Document

10.1016/j.jco.2009.05.002

Cite this

@article{dbb02fbbb0b3469884ba69325363d76a,

title = "On the tractability of linear tensor product problems in the worst case",

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.",

keywords = "Complexity, Multivariate problem, Tractability",

author = "Anargyros Papageorgiou and Iasonas Petras",

year = "2009",

month = oct,

doi = "10.1016/j.jco.2009.05.002",

language = "English (US)",

volume = "25",

pages = "415--419",

journal = "Journal of Complexity",

issn = "0885-064X",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

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

AU - Papageorgiou, Anargyros

AU - Petras, Iasonas

PY - 2009/10

Y1 - 2009/10

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

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

KW - Complexity

KW - Multivariate problem

KW - Tractability

UR - http://www.scopus.com/inward/record.url?scp=69249205586&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=69249205586&partnerID=8YFLogxK

U2 - 10.1016/j.jco.2009.05.002

DO - 10.1016/j.jco.2009.05.002

M3 - Article

AN - SCOPUS:69249205586

SN - 0885-064X

VL - 25

SP - 415

EP - 419

JO - Journal of Complexity

JF - Journal of Complexity

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this