Recent developments in information-based complexity

DOI10.1090/S0273-0979-1987-15511-XzbMATH Open0639.65030OpenAlexW2019405415MaRDI QIDQ3780359FDOQ3780359

Authors: Edward W. Packel, H. Woźniakowski 

Publication date: 1987

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1987-15511-x

Recommendations

• scientific article; zbMATH DE number 953052
• scientific article; zbMATH DE number 3972186
• scientific article; zbMATH DE number 1246413
• Average case optimality
• Do Linear Problems Have Linear Optimal Algorithms?

zbMATH Keywords

linear problemsaverage casenormed linear spaceworst caseinformation-based complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General theory of numerical analysis in abstract spaces (65J05)

Cites Work

• Gaussian measures in Banach spaces
• Title not available (Why is that?)
• A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
• 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?)
• Average case optimal algorithms in Hilbert spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The fundamental theorem of algebra and complexity theory
• Best Approximate Integration Formulas; Best Approximation Formulas
• Computational Complexity and the Existence of Complexity Gaps
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• On the efficiency of algorithms of analysis
• Title not available (Why is that?)
• Sequential Minimax Search for a Maximum
• Optimal solution of nonlinear equations
• Optimal algorithms for linear problems with Gaussian measures
• Information of varying cardinality
• Gaussian measure in Hilbert space and applications in numerical analysis
• On the Regression Design Problem of Sacks and Ylvisaker
• Can adaption help on the average?
• Average case optimality for linear problems
• Average case optimality
• Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• Comparison of iterative methods for the calculation of n th roots
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Probabilistic setting of information-based complexity
• Bisection is optimal
• Optimal sequential and non-sequential procedures for evaluating a functional
• Best approximation of analytic functions from information about their values at a finite number of points
• On the average number of steps of the simplex method of linear programming
• An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
• Are linear algorithms always good for linear problems?
• Linear problems (with extended range) have linear optimal algorithms
• On the existence of generally convergent algorithms
• Title not available (Why is that?)
• R-splines in Banach spaces. I: Interpolation of linear manifolds
• Complexity of differential and integral equations
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• What is the complexity of elliptic systems?
• Optimal Error Properties of Finite Element Methods for Second Order Elliptic Dirichlet Problems
• Title not available (Why is that?)
• Do Linear Problems Have Linear Optimal Algorithms?

Cited In (21)

• The adaption problem for approximating linear operators
• Perspectives on information-based complexity
• Linearity of algorithms and a result of Ando
• The algorithm designer versus nature: A game-theoretic approach to information-based complexity
• On the adaptive and continuous information problems
• There exists a linear problem with infinite combinatory complexity
• s-numbers in information-based complexity
• Title not available (Why is that?)
• Information-based complexity: New questions for mathematicians
• Absolute value information for IBC problems
• Existence of smoothed stationary processes on an interval
• There exists a problem whose computational complexity is any given function of the information complexity
• Continuous problems: optimality, complexity, tractability (invited talk)
• On linearity of spline algorithms
• Measures of uncertainty and information in computation
• Complexity of verification and computation for IBC problems
• How powerful is continuous nonlinear information for linear problems?
• Some basic information on information-based complexity theory
• Title not available (Why is that?)
• Average case optimality
• Title not available (Why is that?)

This page was built for publication: Recent developments in information-based complexity

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