TITLE

Noisy Information and Computational Complexity

AUTHOR(S) SURNAME, FORENAME

Plaskota, Leszek

Places & Countries of PUBLISHERS    YEAR
Publication

Cambridge, UK        Cambridge University    1996
        
        Press

PAGES    ISBN        BINDING    PRICE

xi+308    0-521-55368-7    Hbk    £40

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 mathematical problems for which available information is partial, noisy and priced. The author develops a general theory of computational complexity of continuous problems with noisy information and gives a number of applications; deterministic as well as stochastic noise is considered. He presents optimal algorithms, optimal 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 (affine) algorithms, optimality properties of smoothing spline, regularization and least squares algorithms (with the optimal choice of the smoothing and regularization parameters), adaption

versus non-adaption, and relations between different settings. (From the back cover.)

            31.7.96    4452

Converted using Wp2Html from Andrew Scriven. Copyright Cliff Dilloway on the last date above. The Authors Moral Rights are asserted