Information-based complexity

Information-based complexity (IBC) studies optimal algorithms and computational complexity for the continuous problems that arise in physical science, economics, engineering, and mathematical finance.

Further reading

• Traub, J. F., Iterative Methods for the Solution of Equations, Prentice Hall, 1964. Reissued Chelsea Publishing Company, 1982; Russian translation MIR, 1985; Reissued American Mathematical Society, 1998
• Traub, J. F., and Woźniakowski, H., A General Theory of Optimal Algorithms, Academic Press, New York, 1980
• Traub, J. F., Woźniakowski, H., and Wasilkowski, G. W., Information, Uncertainty, Complexity, Addison-Wesley, New York, 1983
• Novak, E., Deterministic and Stochastic Error Bounds in Numerical Analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, New York, 1988
• Traub, J. F., Woźniakowski, H., and Wasilkowski, G. W. (1988). Information-Based Complexity. New York: Academic Press. ISBN 978-0126975451.
• Werschulz, A. G., The Computational Complexity of Differential and Integral Equations: An Information-Based Approach, Oxford University Press, New York, 1991
• Kowalski, M., Sikorski, K., and Stenger, F., Selected Topics in Approximation and Computation, Oxford University Press, Oxford, UK, 1995
• Plaskota, L., Noisy Information and Computational Complexity, Cambridge University Press, Cambridge, UK, 1996
• Traub, J. F., and Werschulz, A. G., Complexity and Information, Oxford University Press, Oxford, UK, 1998
• Ritter, K., Average-Case Analysis of Numerical Problems, Springer-Verlag, New York, 2000
• Sikorski, K., Optimal Solution of Nonlinear Equations, Oxford University Press, Oxford, UK, 2001

Extensive bibliographies may be found in the monographs N (1988), TW (1980), TWW (1988) and TW (1998). The IBC website has a searchable data base of some 730 items.

External links

• Journal of Complexity
• Complexity and Information
• Joseph Traub
• J.F Traub, 1985. An Introduction to Information-Based Complexity