Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Perspectives on information-based complexity


Authors: J. F. Traub and H. Woźniakowski
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
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • 1. I. Babuška, Information-based numerical practice, J. Complexity (1987), 331-346. MR 919680 (89f:65056)
  • 2. N. S. Bakhvalov, On approximate calculation of integrals, Vestnik Moskov. Gos. Univ. Ser. Mat. Mekh. Astronom. Fiz. Khim. 4 (1959), 3-18. (Russian) MR 0115275 (22:6077)
  • 3. -, 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)
  • 4. -, 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)
  • 5. L. Blum, M. Shub, and S. 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), 1-46. MR 974426 (90a:68022)
  • 6. A. Bojańczyk, Complexity of solving linear systems in different models of computation, SIAM J. Comput. 21 (1984), 591-603. MR 744175 (85g:65056)
  • 7. A. W. Chou, On the optimality of Krylov information, J. Complexity 3 (1987), 26-40. MR 883166 (89a:65051)
  • 8. F. Gao and G. W. Wasilkowski, On detecting regularity of functions, work in progress, 1990.
  • 9. R. M. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness, Freeman, New York, 1979. MR 519066 (80g:68056)
  • 10. M. Golomb and H. F. Weinberger, Optimal approximation and error bounds, On Numerical Approximation (R. E. Langer, ed.), Univ. of Wisconsin Press, Madison, WI, 1959, pp. 117-190. MR 0121970 (22:12697)
  • 11. B. Z. Kacewicz, On sequential and parallel solution of initial value problems, J. Complexity 6 (1990), 136-148. MR 1060642 (91j:65121)
  • 12. B. Z. Kacewicz and L. Plaskota, On the minimal cost of approximating linear problems based on information with deterministic noise, Numer. Funct. Anal. Optim. (1990) (to appear). MR 1079289 (92e:65033)
  • 13. B. Z. Kacewicz and G. W. Wasilkowski, How powerful is continuous nonlinear information for linear problems?, J. Complexity 2 (1986), 306-316. MR 923024 (89a:65099)
  • 14. J. Kiefer, Sequential minimax search for a maximum, Proc. Amer. Math. Soc. 4 (1953), 502-505. MR 0055639 (14:1103h)
  • 15. J. Kuczyński, On the optimal solution of large eigenpair problems, J. Complexity 2 (1986), 131-162. MR 922819 (89a:65062)
  • 16. J. 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).
  • 17. P. Mathé, s-numbers in information-based complexity, J. Complexity 6 (1990), 41-66. MR 1048029 (91e:41042)
  • 18. C. McMullen, Families of rational maps and iterative root-finding algorithms, Ph.D. thesis, Harvard University, Cambridge., MA, 1985.
  • 19. A. S. Nemirovsky, On optimality of Krylov's information when solving linear operator equations, J. Complexity 7 (1991), 121-130. MR 1108772 (92d:65095)
  • 20. A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley-Interscience, New York, 1983. MR 702836 (84g:90079)
  • 21. S. M. Nikolskij, On the problem of approximation estimate by quadrature formulas, Uspekhi. Mat. Nauk 5 (1950), 165-177. (Russian)
  • 22. E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lectures Notes in Math., vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255 (90a:65004)
  • 23. E. W. Packel and J. F. Traub, Information-based complexity, Nature 328 (1987), 29-33.
  • 24. E. W. Packel and H. Woźniakowski, Recent developments in information-based complexity, Bull. Amer. Math. Soc. (N.S.) 17 (1987), 9-36. MR 888879 (88h:65006)
  • 25. B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, NJ, 1980. MR 570116 (81j:65063)
  • 26. -, Some basic information on information-based complexity theory, Bull. Amer. Math. Soc. (N.S.) 26 (1992), 3-27. MR 1102755 (94e:68077a)
  • 27. M. O. Rabin, Solving linear equations by means of scalar products, Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York, 1972, pp. 11-20. MR 0391584 (52:12405)
  • 28. K. F. Roth, On irregularities of distribution, Mathematika 1 (1954), 73-79. MR 0066435 (16:575c)
  • 29. -, On irregularities of distribution. IV, Acta Arith. 37 (1980), 67-75. MR 598865 (82f:10063)
  • 30. A. Sard, Best approximate integration formulas; best approximation formulas, Amer. J. Math. 71 (1949), 80-91. MR 0029283 (10:576a)
  • 31. M. 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.
  • 32. M. Shub and S. Smale, On the existence of generally convergent algorithms, J. Complexity 2 (1986), 2-11. MR 925341 (89d:65054)
  • 33. I. J. Schoenberg, Spline interpolation and best quadrature formulas, Bull. Amer. Math. Soc. 70 (1964), 143-148. MR 0157157 (28:394)
  • 34. E. Stiefel, Kernel polynomials in linear algebra and their numerical applications, NBS Appl. Math. 43 (1958), 1-22. MR 0092214 (19:1080c)
  • 35. J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information, uncertainty, complexity, Addison-Wesley, Reading, MA, 1983.
  • 36. -, Information-based complexity, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • 37. J. F. Traub and H. Woźniakowski, A general theory of optimal algorithms, Academic Press, New York, 1980. MR 584446 (84m:68041)
  • 38. -, On the optimal solution of large linear systems, J. Assoc. Comput. Mach. 31 (1984), 545-559. MR 819157
  • 39. -, Information-based complexity: New questions for mathematicians, Math. Intelligencer 13 (1981), 34-43. MR 1098218
  • 40. G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. 58 (1992), pp. 285-304. MR 1106987 (92f:65027)
  • 41. A. G. Werschulz, The computational complexity of differential and Integral equations, Oxford Univ. Press, Oxford, 1991. MR 1144521 (93a:68061)
  • 42. H. Woźniakowski, A survey of information based-complexity, J. Complexity 1 (1985), 11-44. MR 829868 (87d:68050)
  • 43. -, Average complexity for linear operators over bounded domains, J. Complexity 3 (1987), 57-80. MR 883168 (88h:65040)
  • 44. -, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), 185-194. MR 1072015 (91i:65224)

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2000): 68Q30, 65Y20

Retrieve articles in all journals with MSC (2000): 68Q30, 65Y20


Additional Information

DOI: https://doi.org/10.1090/S0273-0979-1992-00240-9
Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society