Probabilistic complexity analysis for linear problems in bounded domains
From MaRDI portal
Publication:757053
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.
Recommendations
- On the probabilistic complexity of finding an approximate solution for linear programming
- The Probabilistic Theory of Linear Complexity
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- Polynomial-time algorithms for probabilistic solutions of parameter-dependent linear matrix inequalities
- Sharp Bounds on Probabilities Using Linear Programming
- Bounds for probabilistic integer programming problems
- Lower bounds for the complexity of linear functionals in the randomized setting
- A probabilistic approach to problems parameterized above or below tight bounds
- A probabilistic approach to problems parameterized above or below tight bounds
Cites work
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Average complexity for linear operators over bounded domains
- Convex measures on locally convex spaces
- Gaussian characterizations of certain Banach spaces
- Gaussian measures in Banach spaces
- scientific article; zbMATH DE number 3827201 (Why is no real title available?)
- scientific article; zbMATH DE number 3913327 (Why is no real title available?)
- scientific article; zbMATH DE number 3980111 (Why is no real title available?)
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 3712659 (Why is no real title available?)
- scientific article; zbMATH DE number 44104 (Why is no real title available?)
- scientific article; zbMATH DE number 3563703 (Why is no real title available?)
- scientific article; zbMATH DE number 3607229 (Why is no real title available?)
- scientific article; zbMATH DE number 3620605 (Why is no real title available?)
- scientific article; zbMATH DE number 3626044 (Why is no real title available?)
- scientific article; zbMATH DE number 3245885 (Why is no real title available?)
- Invertibility of random fredholm operators
- Mappings of Gaussian Cylindrical Measures in Banach Spaces
Cited in
(13)- Probabilistic setting of information-based complexity
- Corrections to Probabilistic analysis of numerical methods for integral equations
- Lower bounds for the complexity of Monte Carlo function approximation
- Average approximations and moments of measures
- The average case complexity of the Fredholm equation of second kind with free term in H^ r()
- Algorithms and complexity for functions on general domains
- Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness
- A linear-time algorithm for computing the multinomial stochastic complexity
- Probability estimates for reachability of linear systems defined over finite fields
- scientific article; zbMATH DE number 3909744 (Why is no real title available?)
- The worst case complexity of the fredholm equation with periodic free term and noisy information∗
- s-numbers in information-based complexity
- Probabilistic analysis of numerical methods for integral equations
This page was built for publication: Probabilistic complexity analysis for linear problems in bounded domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757053)
