IBC research webpage
People doing research in IBC
Searchable database of IBC literature in BibTeX

Information-based complexity (IBC) is the branch of computational complexity which studies problems for which the information is partial, contaminated, and priced.

To motivate these assumptions about information consider a continuous (as opposed to discrete) dynamical system. It consists of an equation that determines how the system evolves over time and an initial condition. Assume that the equation depends on coefficients that are real functions of a real variable. Since a digital computer can store only a finite set of numbers, these functions must be replaced by such finite sets (by, for example, evaluating the functions at a finite number of points). Therefore, we have only partial information about the equation of evolution and, similarly, about the initial conditions. Furthermore, the function values will be contaminated by round-off error. Finally, evaluating the functions can be expensive.

We regard IBC as a foundational subject and make as few assumptions as possible. We might assume, for example, that the problem is specified by a linear operator and that the information consists of linear functionals. Everything else is a consequence of the theory.

This gives the theory both generality and simplicity, leading to unity across a wide variety of applications.

The applications typically involve multivariate problems of science and engineering. Examples include high dimensional integration, ordinary and partial differential equations, nonlinear optimization, approximation, and ill-posed problems. Although the focus has been on the complexity of computations, the complexity of verification and implementation testing has also been studied.

A number of monographs have been written on IBC. Complexity and Information was published in 1998 in both hard and soft  cover. Its style is informal and the goal is motivations and insight. There is a comprehensive bibliography of over 400 recent papers and books. Precise statements and proofs may be found in Information-Based Complexity, Academic Press, 1988 (with G. Wasilkowski and H. Wozniakowski). Earlier monographs are: Information, Uncertainty, Complexity,  Addison-Wesley, 1983 (with G. Wasilkowski and H. Wozniakowski), and  A General Theory of Optimal Algorithms,  Academic Press, 1980 (with H. . Wozniakowski).

• Sikorski, K., Optimal Solution of Nonlinear Equations, Oxford University Press, Oxford, UK, 1998.
• Keller, A., Quasi-Monte Carlo Methods for Photorealistic Image Synthesis, Shaker, Aachen, 1998.
• Frank, K., Optimal numerical solution of multivariate integral equations, Shaker, Aachen, 1997.
• Plaskota, L., Noisy Information and Computational Complexity, Cambridge University Press, Cambridge, UK, 1996.
• Werschulz, A. G., The Computational Complexity of Differential and Integral Equations: An Information-Based Approach, Oxford University Press, New York, 1991.
• Novak, E., Deterministic and Stochastic Error Bound in Numerical Analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, New York, 1988.

My recent expository papers include:

• Breaking Intractability, Scientific American, 1994 (with H. Wozniakowski). Translated into German, Italian, Japanese, and Polish.
• Recent Progress in Information-Based Complexity, Bulletin European Association Theoretical Computer Science, October, 1993, 142-154 (with H. Wozniakowski).
• Theory and Applications of Information-Based Complexity. Lectures in Complex Systems, Santa Fe Institute Studies in the Sciences of Complexity, Lect. Vol. III (L. Nadel and D. Stein, eds.), Addison-Wesley, Massachusetts, 1991, 163-193 (with H. Wozniakowski).
• Information-Based Complexity: New Questions for Mathematicians, Mathematical Intelligencer, 13, 1991, 34-43 (with H. Wozniakowski).
• Information-Based Complexity , Nature, 327, July, 1987, 29-33 (with E. Packel).