Perspectives on information-based complexity
HTML articles powered by AMS MathViewer
- by J. F. Traub and H. Woźniakowski PDF
- Bull. Amer. Math. Soc. 26 (1992), 29-52 Request permission
References
- I. Babuška, Information-based numerical practice, J. Complexity 3 (1987), no. 3, 331–346. MR 919680, DOI 10.1016/0885-064X(87)90019-7
- N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275 —, On optimal bounds for the convergence of quadrature formulas and Monte-Carlo type integration methods for classes of functions, Numerical Methods for the Solution of Differential and Integral Equations and Quadrature Formulas, Nauka, Moscow, 1964, pp. 5-63. (Russian) —, On the optimality of linear methods for operator approximation in convex classes of functions, U.S.S.R Comput. Math., and Math. Phys. 11 (1971), 244-249. (Russian)
- Lenore Blum, Mike Shub, and Steve Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 1–46. MR 974426, DOI 10.1090/S0273-0979-1989-15750-9
- A. Bojańczyk, Complexity of solving linear systems in different models of computation, SIAM J. Numer. Anal. 21 (1984), no. 3, 591–603. MR 744175, DOI 10.1137/0721041
- Arthur W. Chou, On the optimality of Krylov information, J. Complexity 3 (1987), no. 1, 26–40. MR 883166, DOI 10.1016/0885-064X(87)90003-3 Gao and G. W. Wasilkowski, On detecting regularity of functions, work in progress, 1990.
- Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
- Michael Golomb and Hans F. Weinberger, Optimal approximation and error bounds, On numerical approximation. Proceedings of a Symposium, Madison, April 21-23, 1958, Publication of the Mathematics Research Center, U.S. Army, the University of Wisconsin, no. 1, University of Wisconsin Press, Madison, Wis., 1959, pp. 117–190. Edited by R. E. Langer. MR 0121970
- Bolesław Z. Kacewicz, On sequential and parallel solution of initial value problems, J. Complexity 6 (1990), no. 2, 136–148. MR 1060642, DOI 10.1016/0885-064X(90)90002-U
- B. Z. Kacewicz and L. Plaskota, On the minimal cost of approximating linear problems based on information with deterministic noise, Numer. Funct. Anal. Optim. 11 (1990), no. 5-6, 511–528. MR 1079289, DOI 10.1080/01630569008816386
- B. Kacewicz and G. W. Wasilkowski, How powerful is continuous nonlinear information for linear problems?, J. Complexity 2 (1986), no. 4, 306–316. MR 923024, DOI 10.1016/0885-064X(86)90008-7
- J. Kiefer, Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4 (1953), 502–506. MR 55639, DOI 10.1090/S0002-9939-1953-0055639-3
- Jacek Kuczyński, On the optimal solution of large eigenpair problems, J. Complexity 2 (1986), no. 2, 131–162. MR 922819, DOI 10.1016/0885-064X(86)90016-6 Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, Report, Dept. of Computer Science, Columbia University, 1989 (to appear in SIMAX).
- P. Mathé, $s$-numbers in information-based complexity, J. Complexity 6 (1990), no. 1, 41–66. MR 1048029, DOI 10.1016/0885-064X(90)90011-2 McMullen, Families of rational maps and iterative root-finding algorithms, Ph.D. thesis, Harvard University, Cambridge., MA, 1985.
- A. S. Nemirovsky, On optimality of Krylov’s information when solving linear operator equations, J. Complexity 7 (1991), no. 2, 121–130. MR 1108772, DOI 10.1016/0885-064X(91)90001-E
- A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson. MR 702836 M. Nikolskij, On the problem of approximation estimate by quadrature formulas, Uspekhi. Mat. Nauk 5 (1950), 165-177. (Russian)
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792 W. Packel and J. F. Traub, Information-based complexity, Nature 328 (1987), 29-33.
- Edward W. Packel and Henryk Woźniakowski, Recent developments in information-based complexity, Bull. Amer. Math. Soc. (N.S.) 17 (1987), no. 1, 9–36. MR 888879, DOI 10.1090/S0273-0979-1987-15511-X
- Beresford N. Parlett, The symmetric eigenvalue problem, Prentice-Hall Series in Computational Mathematics, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1980. MR 570116
- Beresford N. Parlett, Some basic information on information-based complexity theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), no. 1, 3–27. MR 1102755, DOI 10.1090/S0273-0979-1992-00239-2
- Michael O. Rabin, Solving linear equations by means of scalar products, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 11–20, 187–212. MR 0391584
- K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73–79. MR 66435, DOI 10.1112/S0025579300000541
- K. F. Roth, On irregularities of distribution. IV, Acta Arith. 37 (1980), 67–75. MR 598865, DOI 10.4064/aa-37-1-67-75
- Arthur Sard, Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71 (1949), 80–91. MR 29283, DOI 10.2307/2372095 Shub, Review of "Information, uncertainty, complexity" by J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski (Addison-Wesley, Reading, MA, 1983), SIAM Re. 29 (1987), 495-496.
- Michael Shub and Steve Smale, On the existence of generally convergent algorithms, J. Complexity 2 (1986), no. 1, 2–11. MR 925341, DOI 10.1016/0885-064X(86)90020-8
- I. J. Schoenberg, Spline interpolation and best quadrature formulae, Bull. Amer. Math. Soc. 70 (1964), 143–148. MR 157157, DOI 10.1090/S0002-9904-1964-11054-5
- Eduard L. Stiefel, Kernel polynomials in linear algebra and their numerical applications, Nat. Bur. Standards Appl. Math. Ser. 49 (1958), 1–22. MR 92214 F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information, uncertainty, complexity, Addison-Wesley, Reading, MA, 1983.
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
- Joe Fred Traub and H. Woźniakowsi, A general theory of optimal algorithms, ACM Monograph Series, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 584446
- J. F. Traub and H. Woźniakowski, On the optimal solution of large linear systems, J. Assoc. Comput. Mach. 31 (1984), no. 3, 545–559. MR 819157, DOI 10.1145/828.830
- J. F. Traub and H. Woźniakowski, Information-based complexity: new questions for mathematicians, Math. Intelligencer 13 (1991), no. 2, 34–43. MR 1098218, DOI 10.1007/BF03024085
- G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. 58 (1992), no. 197, 285–304. MR 1106987, DOI 10.1090/S0025-5718-1992-1106987-X
- Arthur G. Werschulz, The computational complexity of differential and integral equations, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1991. An information-based approach; Oxford Science Publications. MR 1144521
- H. Woźniakowski, A survey of information-based complexity, J. Complexity 1 (1985), no. 1, 11–44. MR 829868, DOI 10.1016/0885-064X(85)90020-2
- H. Woźniakowski, Average complexity for linear operators over bounded domains, J. Complexity 3 (1987), no. 1, 57–80. MR 883168, DOI 10.1016/0885-064X(87)90005-7
- H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Bull. Amer. Math. Soc. 26 (1992), 29-52
- MSC (2000): Primary 68Q30; Secondary 65Y20
- DOI: https://doi.org/10.1090/S0273-0979-1992-00240-9
- MathSciNet review: 1102756