Probabilistic complexity analysis for linear problems in bounded domains

DOI10.1016/0885-064X(90)90021-5zbMATH Open0723.68049MaRDI QIDQ757053FDOQ757053

Authors: Stefan Heinrich 

Publication date: 1990

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

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

zbMATH Keywords

Banach spacelinear problemsinformation-based complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Gaussian measures in Banach spaces
• Title not available (Why is that?)
• Convex measures on locally convex spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mappings of Gaussian Cylindrical Measures in Banach Spaces
• Title not available (Why is that?)
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Average complexity for linear operators over bounded domains
• Title not available (Why is that?)
• Gaussian characterizations of certain Banach spaces
• Invertibility of random fredholm operators
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Probability estimates for reachability of linear systems defined over finite fields
• Algorithms and complexity for functions on general domains
• Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness
• Lower bounds for the complexity of Monte Carlo function approximation
• The worst case complexity of the fredholm equation with periodic free term and noisy information^∗
• Probabilistic setting of information-based complexity
• The average case complexity of the Fredholm equation of second kind with free term in \(H^ r(\Gamma)\)
• A linear-time algorithm for computing the multinomial stochastic complexity
• Probabilistic analysis of numerical methods for integral equations
• Corrections to Probabilistic analysis of numerical methods for integral equations
• Average approximations and moments of measures
• Title not available (Why is that?)

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)