Noisy Information and Computational Complexity
From MaRDI portal
Publication:4229815
DOI10.1017/CBO9780511600814zbMath0923.65101MaRDI QIDQ4229815
Publication date: 28 February 1999
computational complexitytextbookinformation-based complexitynoisy informationoptimal algorithmslinear problemsaverage caseworst caseasymptotic caseinformation and algorithms
Analysis of algorithms and problem complexity (68Q25) General theory of numerical analysis in abstract spaces (65J05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Complexity and performance of numerical algorithms (65Y20)
Related Items
On optimal recovery of values of linear operators from information known with a stochastic error, Optimal recovery of operator sequences, Functional norms, condition numbers and numerical algorithms in algebraic geometry, Learning from non-random data in Hilbert spaces: an optimal recovery perspective, Recovering linear operators and Lagrange function minimality condition, The quantum setting with randomized queries for continuous problems, Computability of solutions of operator equations, Recovering signals from inner products involving prolate spheroidals in the presence of jitter, Unnamed Item, The complexity of Fredholm equations of the second kind: noisy information about everything, Worst case tractability of linear problems in the presence of noise: linear information, A Study on Regularization for Discrete Inverse Problems with Model-Dependent Noise, Informative cardinality of trigonometric Fourier coefficients and their limiting error in the discretization of a differentiation operator in multidimensional Sobolev classes, Optimal recovery methods exact on trigonometric polynomials for the solution of the heat equation, Joint spectra of Toeplitz operators and optimal recovery of analytic functions, Optimal recovery from inaccurate data in Hilbert spaces: regularize, but what of the parameter?, On Linear Versus Nonlinear Approximation in the Average Case Setting, A lower bound on convergence rates of nonadaptive algorithms for univariate optimization with noise, A survey of average case complexity for linear multivariate problems, A stochastically quasi-optimal search algorithm for the maximum of the simple random walk, Exact orders of computational (numerical) diameters in problems of reconstructing functions and sampling solutions of the Klein-Gordon equation from Fourier coefficients, Optimal recovery methods for solutions of the Dirichlet problem that are exact on subspaces of spherical harmonics, Automatic integration using asymptotically optimal adaptive simpson quadrature, Instances of Computational Optimal Recovery: Dealing with Observation Errors, Optimal conditional estimation: Average case setting, The power of adaption for approximating functions with singularities, Computational (numerical) diameter in a context of general theory of a recovery, Optimal recovery of operators in function \(L\)-spaces, Spatial shape-preserving interpolation using \(\nu\)-splines, On the power of standard information for \(L_{\infty}\) approximation in the randomized setting, The power of standard information for multivariate approximation in the randomized setting, Adaption allows efficient integration of functions with unknown singularities, Spatial adaption for predicting random functions, On the optimal robust solution of IVPs with noisy information
