A survey of information-based complexity
From MaRDI portal
Publication:1080661
DOI10.1016/0885-064X(85)90020-2zbMath0599.68045OpenAlexW2098826948MaRDI QIDQ1080661
Publication date: 1985
Published in: Journal of Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0885-064x(85)90020-2
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02)
Related Items
Optimal solution of nonlinear equations, Sampling discretization and related problems, On the existence of optimal affine methods for approximating linear functionals, Optimal solution of ordinary differential equations, Information-based numerical practice, Some basic information on information-based complexity theory, Perspectives on information-based complexity, Local adaption for approximation and minimization of univariate functions, On a class of omnibus algorithms for zero-finding, Optimal search algorithm for extrema of a discrete periodic bimodal function, Optimal algorithms for a problem of optimal control, Parallel information-based complexity, A modern retrospective on probabilistic numerics, Information based complexity for high dimensional sparse functions, Integral norm discretization and related problems, Information of varying cardinality, On average case errors in numerical analysis, Optimal recovery of functionals based on inaccurate data, Average case optimality
Cites Work
- How to increase the order to get minimal-error algorithms for systems of ODE
- Can adaption help on the average?
- Average case optimality for linear problems
- Measuring uncertainty without a norm
- Optimality of Euler-integral information for solving a scalar autonomous ODE
- What is the complexity of elliptic systems?
- Optimal algorithms for image understanding: Current status and future plans
- Average case optimality
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Complexity of differential and integral equations
- Optimal solution of nonlinear equations
- Coping with errors in binary search procedures
- Complexity of linear programming
- Bisection is optimal
- On the optimal error of algorithms for solving scalar autonomous ODE
- Best approximation of analytic functions from information about their values at a finite number of points
- Estimating the quality of computational algorithms. I
- Information of varying cardinality
- Some nonlinear problems are as easy as the approximation problem
- A general method for the construction of interpolating or smoothing spline-functions
- R-splines in Banach spaces. I: Interpolation of linear manifolds
- On the Optimal Solution of Large Linear Systems
- Optimal sequential and non-sequential procedures for evaluating a functional
- Perspectives on information-based complexity
- On the optimality of linear methods for operator approximation in convex classes of functions
- Computational Complexity and the Existence of Complexity Gaps
- Best Approximate Integration Formulas; Best Approximation Formulas
- Sequential Minimax Search for a Maximum
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
