A survey of information-based complexity

DOI10.1016/0885-064X(85)90020-2MaRDI QIDQ1080661zbMATH OpenOpenAlexFDO

Authors H. Woźniakowski

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

zbMATH Keywords

average casesurveyworst case

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)

Review text

We survey some recent results in information-based complexity. We focus on the worst case setting and also indicate some average case results.

Cites work

• A general method for the construction of interpolating or smoothing spline-functions
• Approximation of linear functionals on a Banach space with a Gaussian measure
• Average case optimality
• Average case optimality for linear problems
• Best Approximate Integration Formulas; Best Approximation Formulas
• Best approximation of analytic functions from information about their values at a finite number of points
• Bisection is optimal
• Can adaption help on the average?
• Complexity of differential and integral equations
• Complexity of linear programming
• Computational Complexity and the Existence of Complexity Gaps
• Coping with errors in binary search procedures
• Estimating the quality of computational algorithms. I
• How to increase the order to get minimal-error algorithms for systems of ODE
• scientific article; zbMATH DE number 3150148 (Why is no real title available?)
• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 3827201 (Why is no real title available?)
• scientific article; zbMATH DE number 3914022 (Why is no real title available?)
• scientific article; zbMATH DE number 3932991 (Why is no real title available?)
• scientific article; zbMATH DE number 4112013 (Why is no real title available?)
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 3460859 (Why is no real title available?)
• scientific article; zbMATH DE number 3464842 (Why is no real title available?)
• scientific article; zbMATH DE number 3601500 (Why is no real title available?)
• scientific article; zbMATH DE number 3206529 (Why is no real title available?)
• scientific article; zbMATH DE number 3321507 (Why is no real title available?)
• scientific article; zbMATH DE number 3055587 (Why is no real title available?)
• Information of varying cardinality
• Measuring uncertainty without a norm
• On the optimal error of algorithms for solving scalar autonomous ODE
• On the Optimal Solution of Large Linear Systems
• On the optimality of linear methods for operator approximation in convex classes of functions
• Optimal algorithms for image understanding: Current status and future plans
• Optimal sequential and non-sequential procedures for evaluating a functional
• Optimal solution of nonlinear equations
• Optimality of Euler-integral information for solving a scalar autonomous ODE
• Perspectives on information-based complexity
• R-splines in Banach spaces. I: Interpolation of linear manifolds
• Sequential Minimax Search for a Maximum
• Some nonlinear problems are as easy as the approximation problem
• What is the complexity of elliptic systems?

Cited in

(22)

• Average case optimality
• Optimal solution of nonlinear equations
• On the existence of optimal affine methods for approximating linear functionals
• Optimal solution of ordinary differential equations
• Information-based numerical practice
• 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
• Optimal recovery of functionals based on inaccurate data
• Information of varying cardinality
• On average case errors in numerical analysis
• Sampling discretization and related problems
• A modern retrospective on probabilistic numerics
• Information based complexity for high dimensional sparse functions
• Local adaption for approximation and minimization of univariate functions
• Some basic information on information-based complexity theory
• Perspectives on information-based complexity
• scientific article; zbMATH DE number 922628 (Why is no real title available?)
• Integral norm discretization and related problems
• scientific article; zbMATH DE number 5583062 (Why is no real title available?)
• Sampling recovery on classes defined by integral operators and sparse approximation with adaptive dictionaries

This page was built for publication: A survey of information-based complexity

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