Complexity of multilinear problems in the average case setting

DOI10.1016/0885-064X(91)90047-2MaRDI QIDQ1174451zbMATH OpenOpenAlexFDO

Authors Tomasz Jackowski

Publication date 25 June 1992

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064x(91)90047-2

zbMATH Keywords

algorithmHilbert spaceBanach spacesworst case settingaverage case settingaverage performancemultilinear problemsspline algorithms

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical linear algebra (65F99) Communication theory (94A05) Information theory (general) (94A15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Communication, information (94A99) Numerical solutions to equations with linear operators (65J10)

Recommendations

• Average case complexity of linear multivariate problems
• Average case complexity of linear multivariate problems. II: Applications
• Average case complexity of linear multivariate problems. I: Theory
• A survey of average case complexity for linear multivariate problems
• On the average complexity of multivariate problems
• Complexity of multilinear problems in the worst case setting
• Tractability of linear multivariate problems in the average case setting
• Average case tractability of a multivariate approximation problem
• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• Quasi-polynomial tractability of linear problems in the average case setting

Cites work

• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3245885 (Why is no real title available?)
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Can adaption help on the average?
• Complexity of multilinear problems in the worst case setting
• Elliptically contoured measures on infinite-dimensional Banach spaces
• On the average complexity of multivariate problems
• Orthogonally invariant measures and best approximation of linear operators

Cited in

(9)

• Average-case lower bounds for the plurality problem
• Average case complexity of linear multivariate problems
• Complexity of multilinear problems in the worst case setting
• Information-based complexity: New questions for mathematicians
• Average case optimality for linear problems
• Average-case complexity of the min-sum matrix product problem
• Polynomial-time algorithms for multivariate linear problems with finite-order weights: Average case setting
• Average case tractability of a multivariate approximation problem
• lnκ-weak tractability of general multivariate problems in the average case setting

This page was built for publication: Complexity of multilinear problems in the average case setting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1174451)