This book contains five essays on the complexity of continuous problems, written for a wider audience. The first four essays are based on talks presented in 2008 when Henryk Wozniakowski received an honorary doctoral degree from the Friedrich Schiller University of Jena. The focus is on the introduction and history of the complexity of continuous problems, as well as on recent progress concerning the complexity of high-dimensional numerical problems. The last essay provides a brief and informal introduction to the basic notions and concepts of information-based complexity addressed to a general readership.

This is the second of a series of papers in which we construct an information based general theory of optimal error algorithms and analytic computational complexity and study applications of the general theory. In our first paper we studied a general information' model; here we study an 'iterative information' model. We give a general paradigm, based on the pre-image set of an information operator, for obtaining a lower bound on the error of any algorithm using this information. We show that the order of information provides an upper bound on the order of any algorithm using this information. This upper bound order leads to a lower bound on the complexity index.

New and classical results in computational complexity, including interactive proofs, PCP, derandomization, and quantum computation. Ideal for graduate students.

These five volumes bring together a wealth of bibliographic information in the area of numerical analysis. Containing over 17,600 reviews of articles, books, and conference proceedings, these volumes represent all the numerical analysis entries that appeared in Mathematical Reviews between 1980 and 1986. Author and key indexes appear at the end of volume 5.