Bulletin of the American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Help
ISSN 1088-9485(e) ISSN 0273-0979(p)

Perspectives on information-based complexity

Author(s): J. F. Traub; H. Woźniakowski
Journal: Bull. Amer. Math. Soc. 26 (1992), 29-52.
MSC (2000): Primary 68Q30; Secondary 65Y20
MathSciNet review: 1102756
Retrieve article in: PDF

References:

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)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|