|
Perspectives on Information-Based Complexity
Author(s):
J.
F.
Traub;
H.
Wo\'zniakowski
Journal:
Bull. Amer. Math. Soc.
26
(1992),
29-52.
MSC (1991):
Primary 68Q25
MathSciNet review:
1102756
Retrieve article in:
PDF
References |
Similar articles |
Additional information
References:
- *
- I. Babu\u ska, Information-based numerical practice, J. Complexity (1987), 331--346. MR 919680
- *
- N. S. Bakhvalov, On approximate calculation of integrals, Vestnik Moskov. Gos. Univ. Ser. Mat. Mekh. Astronom. Fiz. Khim. \textbf{4} (1959), 3--18. ({Russian}) MR 115275
- *
- N. S. Bakhvalov, \RM {Numerical Methods for the Solution of Differential and Integral Equations and Quadrature Formulas }, ``Nauka,'' Moscow, 1964, pp.~5--63. (Russian) MR
- *
- N. S. Bakhvalov, On the optimality of linear methods for operator approximation in convex classes of functions, Zh. Vychisl. Mat. Mat. Fiz. \textbf{11} (1971), 1014--1018. MR 290523
- *
- L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers\,\RM : NP-completeness, recursive functions and universal machines, Bull. Amer. Math. Soc. (N.S.) \textbf{21} (1989), 1--46. MR 974426
- *
- A. Boja\'nczyk, Complexity of solving linear systems in different models of computation, SIAM J. Comput. \textbf{21} (1984), 591--603. MR 744175
- *
- A. W. Chou, On the optimality of Krylov information, J. Complexity \textbf{3} (1987), 26--40. MR 883166
- *
- F. Gao and G. W. Wasilkowski, On detecting regularity of functions, work in progress, 1990. MR
- *
- R. M. Garey and D. S. Johnson, Computers and intractability\,\RM : A guide to the theory of NP-completeness, Freeman, New York, 1979. MR 519066
- *
- M. Golomb and H. F. Weinberger, \RM {On Numerical Approximation (R. E. Langer, ed.)}, Univ. of Wisconsin Press, Madison, WI, 1959, pp.~117--190. MR 121970
- *
- B. Z. Kacewicz, On sequential and parallel solution of initial value problems, J. Complexity \textbf{6} (1990), 136--148. MR 1060642
- *
- 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). MR 1079289
- *
- B. Z. Kacewicz and G. W. Wasilkowski, How powerful is continuous nonlinear information for linear problems\,\RM ?, J. Complexity \textbf{2} (1986), 306--316. MR 923024
- *
- J. Kiefer, Sequential minimax search for a maximum, Proc. Amer. Math. Soc. \textbf{4} (1953), 502--505. MR 55639
- *
- J. Kuczy\'nski, On the optimal solution of large eigenpair problems, J. Complexity \textbf{2} (1986), 131--162. MR 922819
- *
- J. Kuczy\'nski and H. Wo\'zniakowski, 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). MR 1182715
- *
- P. Math\'e, s-numbers in information-based complexity, J. Complexity \textbf{6} (1990), 41--66. MR 1048029
- *
- C. McMullen, Families of rational maps and iterative root-finding algorithms, Ph.D. thesis, Harvard University, Cambridge, MA, 1985. MR
- *
- A. S. Nemirovsky, On optimality of Krylov's information when solving linear operator equations, J. Complexity {\bf 7} (1991), 121--130. MR 1108772
- *
- A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization, Wiley-Interscience, New York, 1983. MR 702836
- *
- S. M. Nikolski\u \i, On the problem of approximation estimate by quadrature formulas, Uspekhi. Mat. Nauk \textbf{5} (1950), 165--177. (Russian) MR 36276
- *
- E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lectures Notes in Math., vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255
- *
- E. W. Packel and J. F. Traub, Information-based complexity, Nature \textbf{328} (1987), 29--33. MR
- *
- E. W. Packel and H. Wo\'zniakowski, Recent developments in information-based complexity, Bull. Amer. Math. Soc. (N.S.) \textbf{17} (1987), 9--36. MR 888879
- *
- B. N. Parlett, The symmetric eigenvalue problem, Prentice-Hall, Englewood Cliffs, NJ, 1980. MR 570116
- *
- B. N. Parlett, Some basic information on information-based complexity theory, Bull. Amer. Math. Soc. (N.S.) {\bf 26} (1992), 3--27. MR 1102755
- *
- M. O. Rabin, \RM {Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), Plenum Press, New York }, 1972, pp.~11--20. MR 391584
- *
- K. F. Roth, On irregularities of distribution, Mathematika \textbf{1} (1954), 73--79. MR 66435
- *
- K. F. Roth, On irregularities of distribution. \RM {IV}, Acta Arith. \textbf{37} (1980), 67--75. MR 598865
- *
- A. Sard, Best approximate integration formulas\,\RM ; best approximation formulas, Amer. J. Math. \textbf{71} (1949), 80--91. MR 29283
- *
- M. Shub, \RM {Review of} \RM {``}Information, uncertainty, complexity \RM {'' by J. F. Traub, G. W. Wasilkowski, and H. Wo\'zniakowski (Addison-Wesley, Reading, MA, 1983\/)}, SIAM Re. \textbf{29} (1987), 495--496. MR
- *
- M. Shub and S. Smale, On the existence of generally convergent algorithms, J. Complexity \textbf{2} (1986), 2--11. MR 925341
- *
- I. J. Schoenberg, Spline interpolation and best quadrature formulas, Bull. Amer. Math. Soc. \textbf{70} (1964), 143--148. MR 157157
- *
- E. Stiefel, Kernel polynomials in linear algebra and their numerical applications, NBS Appl. Math. \textbf{43} (1958), 1--22. MR 92214
- *
- J. F. Traub, G. W. Wasilkowski, and H. Wo\'zniakowski, Information, uncertainty, complexity, Addison-Wesley, Reading, MA, 1983. MR 680041
- *
- J. F. Traub, G. W. Wasilkowski, and H. Wo\'zniakowski, Information-based complexity, Academic Press, New York, 1988. MR 958691
- *
- J. F. Traub and H. Wo\'zniakowski, A general theory of optimal algorithms, Academic Press, New York, 1980. MR 584446
- *
- J. F. Traub and H. Wo\'zniakowski, On the optimal solution of large linear systems, J. Assoc. Comput. Mach. \textbf{31} (1984), 545--559. MR 819157
- *
- J. F. Traub and H. Wo\'zniakowski, Information-based complexity\,\RM : New questions for mathematicians, Math. Intelligencer {\bf 13} (1981), 34--43. MR 1098218
- *
- G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities, Math. Comp. {\bf 58} (1992), pp. 285--304. MR 1106987
- *
- A. G. Werschulz, The computational complexity of differential and integral equations, Oxford Univ. Press, Oxford, 1991. MR 1144521
- *
- H. Wo\'zniakowski, A survey of information based-complexity, J. Complexity \textbf{1} (1985), 11--44. MR 829868
- *
- H. Wo\'zniakowski, Average complexity for linear operators over bounded domains, J. Complexity \textbf{3} (1987), 57--80. MR 883168
- *
- H. Wo\'zniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) \textbf{24} (1991), 185--194. MR 1072015
Similar Articles:
Retrieve articles in Bulletin of the American Mathematical Society
with MSC
(1991):
68Q25
Retrieve articles in all Journals with MSC
(1991):
68Q25
Additional Information:
DOI:
10.1090/S0273-0979-1992-00240-9
PII:
S 0273-0979(1992)00240-9
|
