Recent developments in information-based complexity
From MaRDI portal
Publication:3780359
DOI10.1090/S0273-0979-1987-15511-XzbMath0639.65030OpenAlexW2019405415MaRDI QIDQ3780359
Edward W. Packel, Henryk 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
Analysis of algorithms and problem complexity (68Q25) General theory of numerical analysis in abstract spaces (65J05)
Related Items
The algorithm designer versus nature: A game-theoretic approach to information-based complexity, Some basic information on information-based complexity theory, Perspectives on information-based complexity, The adaption problem for approximating linear operators, Existence of smoothed stationary processes on an interval, Linearity of algorithms and a result of Ando, Measures of uncertainty and information in computation, On the adaptive and continuous information problems, Information-based complexity: New questions for mathematicians, s-numbers in information-based complexity, On linearity of spline algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Can adaption help on the average?
- Average case optimality for linear problems
- What is the complexity of elliptic systems?
- Average case optimality
- Average case optimal algorithms in Hilbert spaces
- On the existence of generally convergent algorithms
- Monte-Carlo algorithms for the planar multiterminal network reliability problem
- Approximation of linear functionals on a Banach space with a Gaussian measure
- Are linear algorithms always good for linear problems?
- Complexity of differential and integral equations
- Optimal solution of nonlinear equations
- Optimal algorithms for linear problems with Gaussian measures
- Probabilistic setting of information-based complexity
- Linear problems (with extended range) have linear optimal algorithms
- Bisection is optimal
- Gaussian measures in Banach spaces
- Best approximation of analytic functions from information about their values at a finite number of points
- Information of varying cardinality
- R-splines in Banach spaces. I: Interpolation of linear manifolds
- Gaussian measure in Hilbert space and applications in numerical analysis
- Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
- On the average number of steps of the simplex method of linear programming
- Comparison of iterative methods for the calculation of n th roots
- Do Linear Problems Have Linear Optimal Algorithms?
- On the efficiency of algorithms of analysis
- Computational complexity. On the geometry of polynomials and a theory of cost. I
- Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
- An algorithm to solve them ×n assignment problem in expected timeO(mn logn)
- Optimal sequential and non-sequential procedures for evaluating a functional
- The fundamental theorem of algebra and complexity theory
- Optimal Error Properties of Finite Element Methods for Second Order Elliptic Dirichlet Problems
- A Correspondence Between Bayesian Estimation on Stochastic Processes and Smoothing by Splines
- On the Regression Design Problem of Sacks and Ylvisaker
- Computational Complexity and the Existence of Complexity Gaps
- Best Approximate Integration Formulas; Best Approximation Formulas
- Sequential Minimax Search for a Maximum
