L. Plaskota

Noisy Information and Computational Complexity

---

This is the first book in which noisy information is studied in the context of computational complexity, in other words it deals with the computational complexity of problems for which available information is partial, noisy and priced. The author develops a general theory and gives a number of applications; deterministic as well as stochastic noise is considered. He presents optimal algorithms, information, and complexity bounds in different settings; worst case, average case, mixed worst-average and average-worst, and asymptotic. Particular topics include the existence of optimal linear algorithms, optimality properties of smoothing spline, regularization and least squares algorithms, adaption versus nonadaption. The book integrates the work of researchers in computational complexity, approximation theory and statistics, and includes many new results as well. About two hundred exercises are supplied. It can be used either as a textbook, or as a standard reference.

---

  Table of contents

  1   Overview

  2   Worst case setting

    2.1   Introduction
    2.2   Information, algorithms, approximation
    2.3   Radius and diameter of information
    2.4   Affine algorithms for linear functionals
    2.5   Optimality of spline algorithms
    2.6   Special splines
    2.7   Varying information
    2.8   Optimal nonadaptive information
    2.9   Complexity
    2.10   Complexity of special problems

  3   Average case setting

    3.1   Introduction
    3.2   Information and its radius
    3.3   Gaussian measures on Banach spaces
    3.4   Linear problems with gaussian measures
    3.5   The case of linear functionals
    3.6   Optimal algorithms as smoothing splines
    3.7   Varying information
    3.8   Optimal nonadaptive information
    3.9   Complexity
    3.10   Complexity of special problems

  4   Worst-average case setting

    4.1   Introduction
    4.2   Affine algorithms for linear functionals
    4.3   Approximation of operators

  5   Average-worst case setting

    5.1   Introduction
    5.2   Linear algorithms for linear functionals
    5.3   Approximation of operators

  6   Asymptotic setting

    6.1   Introduction
    6.2   Asymptotic and worst case settings
    6.3   Asymptotic and average case setting

---