Probabilistic complexity analysis for linear problems in bounded domains
type: Item
instance of: scholarly article
title: Probabilistic complexity analysis for linear problems in bounded domains
zbMATH Open document ID: 0723.68049
DOI: 10.1016/0885-064X(90)90021-5
author: Stefan Heinrich
published in: Journal of Complexity
publication date: 1990-01-01T00:00:00Z
review text: In the study of information-based complexity let p be the probabilistic complexity for solving a problem on a bounded domain. The p can be interpreted as the minimal number of information operations needed to solve the problem with the given precision requirement. Using tools from the Banach space theory, the author provides two-sided estimates of p with upper and lower bounds differing only by a constant factor, for the approximation of functions of the periodic Sobolev class in the Hilbert space.
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 4193118
zbMATH Keywords: linear problems
zbMATH Keywords: information-based complexity
zbMATH Keywords: Banach space
MaRDI profile type: Publication
cites work: Convex measures on locally convex spaces
cites work: Q4172686
cites work: Gaussian characterizations of certain Banach spaces
cites work: Invertibility of random fredholm operators
cites work: Q3903573
cites work: Gaussian measures in Banach spaces
cites work: Approximation of linear functionals on a Banach space with a Gaussian measure
cites work: Mappings of Gaussian Cylindrical Measures in Banach Spaces
cites work: Q4136031
cites work: Q4188284
cites work: Q5533878
cites work: Q4183861
cites work: Q3744958
cites work: Q3673103
cites work: Q3993279
cites work: Q3883494
cites work: Q3689920
cites work: Average complexity for linear operators over bounded domains
Recommended article: On the probabilistic complexity of finding an approximate solution for linear programming
Recommended article: The Probabilistic Theory of Linear Complexity
Recommended article: Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
Recommended article: Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities
Recommended article: Sharp Bounds on Probabilities Using Linear Programming
Recommended article: Bounds for probabilistic integer programming problems
Recommended article: Lower bounds for the complexity of linear functionals in the randomized setting
Recommended article: A probabilistic approach to problems parameterized above or below tight bounds
Recommended article: A Probabilistic Approach to Problems Parameterized above or below Tight Bounds
description: scientific article; zbMATH DE number 4193118