scientific article; zbMATH DE number 193625
From MaRDI portal
Publication:4040428
The book is about information-based complexity theory - in contrast to computational complexity theory. The central notion here is that of information - roughly meaning the amount of knowledge about the computational problem to be solved. In practical applications, information about problems is either partial or noisy. For such problems, only approximate solutions are possible. This book constitutes a very general theory to deal with this situation. The gaining of information about a problem in question is considered to be priced, leading to the notion of cost of an algorithm. The cost and the approximation error of algorithms can be variously defined, leading to 3 major different settings studied in this book: the worst case, the average case, and the probabilistic setting.
Recommendations
Cited in
(only showing first 100 items - show all)- Optimal recovery on the classes of functions with bounded mixed derivative
- On the power of standard information for \(L_{\infty}\) approximation in the randomized setting
- Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
- Average case optimality
- The algorithm designer versus nature: A game-theoretic approach to information-based complexity
- Corrections to Probabilistic analysis of numerical methods for integral equations
- Measures of uncertainty and information in computation
- The convergence rate of the sandwich algorithm for approximating convex functions
- Average errors for zero finding: Lower bounds
- Average case complexity of elliptic partial differential equations
- Uniform reconstruction of Gaussian processes
- Feasible real random access machines
- Asymptotic minimax risk for sup-norm loss: Solution via optimal recovery
- Optimal stochastic quadrature formulas for convex functions
- Average errors for zero finding: Lower bounds for smooth or monotone functions
- Worst case identification of continuous time systems via interpolation
- Linear ill-posed problems are solvable on the average for all Gaussian measures
- Recursive characterization of computable real-valued functions and relations
- Integration and \(L_ 2\)-approximation: Average case setting with isotropic Wiener measure for smooth functions
- Model quality evaluation in set membership identification
- Polya's characterization theorem for complex random variables
- The size of the membership-set in a probabilistic framework.
- A stochastically quasi-optimal search algorithm for the maximum of the simple random walk
- A study on the average case error of composite Newton-Cotes quadratures.
- Real computations with fake numbers
- Efficient finite-dimensional solution of initial value problems in infinite-dimensional Banach spaces
- The curse of dimensionality for numerical integration on general domains
- Asymptotically tight worst case complexity bounds for initial-value problems with nonadaptive information
- Tractability of \(\mathbb{L}_2\)-approximation in hybrid function spaces
- Efficient solution of IVPs with right-hand sides having discontinuities on an unknown hypersurface
- On the optimal recovery of integrals of set-valued functions
- Multivariate approximation for analytic functions with Gaussian kernels
- Efficient approximate solution of jump-diffusion SDEs via path-dependent adaptive step-size control
- Optimal Monte Carlo methods for \(L^2\)-approximation
- Probabilistic and average linear widths of weighted Sobolev spaces on the ball equipped with a Gaussian measure
- The difficulty of Monte Carlo approximation of multivariate monotone functions
- Simple characterizations of exponential tractability for linear multivariate problems
- Optimal quadrature formulas for the Sobolev space H^1
- Near-optimality of linear recovery from indirect observations
- Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness
- On the complexity of computing the \(L_q\) norm
- The information capacity of hypercycles
- The optimal uniform approximation of systems of stochastic differential equations
- From Monte Carlo to quantum computation
- Step size control for the uniform approximation of systems of stochastic differential equations with additive noise.
- Worst-case optimality of smoothing algorithms for parametric system identification
- Testing linear operators
- Estimation of model quality
- Worst-case control-relevant identification
- Bounded-error parameter estimation: Noise models and recursive algorithms
- Tractability of the Fredholm problem of the second kind
- Unfalsified model parametrization based on frequency domain noise information
- Global optimization with space-filling curves.
- Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals
- A note on Korobov lattice rules for integration of analytic functions
- Integration and approximation in cosine spaces of smooth functions
- Integral equations and machine learning
- Solvable integration problems and optimal sample size selection
- Tractability of multivariate approximation over weighted standard Sobolev spaces
- Generalized adaptive versus nonadaptive recovery from noisy information
- Central configurations in planar n-body problem with equal masses for n=5,6,7
- On a randomized backward Euler method for nonlinear evolution equations with time-irregular coefficients
- Optimal approximation of stochastic integrals in analytic noise model
- Computation of the output of a function with fuzzy inputs based on a low-rank tensor approximation
- Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
- Tractability for Volterra problems of the second kind with convolution kernels
- Randomized Runge-Kutta method -- stability and convergence under inexact information
- Estimates of entropy numbers in probabilistic setting
- Automatic approximation using asymptotically optimal adaptive interpolation
- Complexity and tractability for a class of elliptic partial integro-differential equations
- On the randomized Euler schemes for ODEs under inexact information
- Fully polynomial time (,)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs
- On linear spline algorithms of computerized tomography in the space of n-orbits
- On the power of standard information for tractability for \(L_2\)-approximation in the average case setting
- Optimal recovery of operator sequences
- Sampling discretization and related problems
- Optimal global approximation of systems of jump-diffusion SDEs on equidistant mesh
- (s, t)-weak tractability of multivariate linear problems in the average case setting
- EC-(t₁,t₂)-tractability of approximation in weighted Korobov spaces in the worst case setting
- Optimal randomized quadrature for weighted Sobolev and Besov classes with the Jacobi weight on the ball
- On the power of standard information for \(\mathbb{L}_2\)-approximation in the average case setting
- Complexity of approximating Hölder classes from information with varying Gaussian noise
- Randomized derivative-free Milstein algorithm for efficient approximation of solutions of SDEs under noisy information
- Lower bounds for finding stationary points I
- On efficient weighted integration via a change of variables
- Complexity of parametric initial value problems for systems of odes
- Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture
- A note on EC-tractability of multivariate approximation in weighted Korobov spaces for the standard information class
- Rounding on the standard simplex: regular grids for global optimization
- Complexity of parametric initial value problems in Banach spaces
- Uniform weak tractability
- The cost of deterministic, adaptive, automatic algorithms: cones, not balls
- Quasi-polynomial tractability of linear problems in the average case setting
- Minimal asymptotic error for one-point approximation of SDEs with time-irregular coefficients
- Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness
- Absolute value information for IBC problems
- Computational (numerical) diameter in a context of general theory of a recovery
- Sampling numbers of a class of infinitely differentiable functions
- Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
- \( \varepsilon \)-superposition and truncation dimensions in average and probabilistic settings for \(\infty \)-variate linear problems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4040428)
