{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:55:13Z","timestamp":1649004913985},"reference-count":56,"publisher":"Elsevier","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1984]]},"DOI":"10.1016\/s0065-2458(08)60462-3","type":"book-chapter","created":{"date-parts":[[2011,1,19]],"date-time":"2011-01-19T05:56:15Z","timestamp":1295416575000},"page":"35-92","source":"Crossref","is-referenced-by-count":8,"title":["Information and Computation"],"prefix":"10.1016","author":[{"given":"J.F.","family":"Traub","sequence":"first","affiliation":[]},{"given":"H.","family":"Wo\u017aniakowski","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0065-2458(08)60462-3_bib1","first-page":"1970","article-title":"Uniqueness in the inversion of inaccurate gross earth data","volume":"266","author":"Backus","year":"1970","journal-title":"Philos. Soc. Trans. London"},{"key":"10.1016\/S0065-2458(08)60462-3_bib2_1","first-page":"1014","article-title":"On the optimality of linear methods for operator approximation in convex classes of functions","volume":"11","author":"Bakhvalov","year":"1971","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"10.1016\/S0065-2458(08)60462-3_bib2_2","first-page":"244","volume":"11","year":"1971","journal-title":"USSR Comput. Math. Math. Phys. (Engl. Transl.)"},{"key":"10.1016\/S0065-2458(08)60462-3_bib3","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF02161361","article-title":"Asymptotic properties of minimum norm and optimal quadratures","volume":"12","author":"Barnhill","year":"1968","journal-title":"Numer. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib4","doi-asserted-by":"crossref","unstructured":"Belforte, G., Milanese, M., and Tempo, R. (1982). \u201cOptimal Algorithm Theory and Estimation with Unknown but Bounded Error.\u201d Dipartimento Di Automatica-Informatica Report, Politecnico Di Torino, Italy.","DOI":"10.1109\/CDC.1982.268254"},{"key":"10.1016\/S0065-2458(08)60462-3_bib5","first-page":"441","article-title":"Best quadrature formula for a certain class of analytic functions","volume":"14","author":"Bojanov","year":"1974","journal-title":"Zastosow. Mat."},{"key":"10.1016\/S0065-2458(08)60462-3_bib6","series-title":"Some Mathematical Topics in Seismology","author":"Burridge","year":"1974"},{"key":"10.1016\/S0065-2458(08)60462-3_bib7","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1080\/00036818008839292","article-title":"Optimal sequential and non-sequential procedures for evaluating a functional","volume":"10","author":"Gal","year":"1980","journal-title":"Appl. Anal."},{"key":"10.1016\/S0065-2458(08)60462-3_bib8","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/S0065-2458(08)60462-3_bib9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/BF01409958","article-title":"An integral-interpolation iterative method for the solution of scalar equations","volume":"26","author":"Kacewicz","year":"1976","journal-title":"Numer. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib10","series-title":"Analytic Computational Complexity","first-page":"127","article-title":"The use of integrals in the solution of nonlinear equations in N dimensions","author":"Kacewicz","year":"1976"},{"key":"10.1016\/S0065-2458(08)60462-3_bib11","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1145\/322123.322129","article-title":"Integrands with a kernel in the solution of nonlinear equations in N dimensions","volume":"26","author":"Kacewicz","year":"1979","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0065-2458(08)60462-3_bib12","unstructured":"Kadane, J., and Wasilkowski, G. W. (1983). Average case \u025b-complexity: A Bayesian view. Valencia Int. Meet. Bayesian Stat., 2nd, 1983."},{"key":"10.1016\/S0065-2458(08)60462-3_bib13","unstructured":"Karmarkar, N., and Karp, R. M. (1982). An efficient approximation scheme for the onedimensional bin-packing problem. 23rd Annu. Symp. Found. Comput. Sci. pp. 312\u2013320."},{"key":"10.1016\/S0065-2458(08)60462-3_bib14","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1090\/S0002-9939-1953-0055639-3","article-title":"Sequential minimax search for a maximum","volume":"4","author":"Kiefer","year":"1953","journal-title":"Proc. Am. Math. Soc."},{"key":"10.1016\/S0065-2458(08)60462-3_bib15","unstructured":"Kowalski, M. A., Werschluz, A. G., and Wo\u017aniakowski, H. (1983). \u201cIs Gauss Quadrature Optimal for Analytic Functions?\u201d Rep. Division of Science and Mathematics, Fordham University and Dept. of Computer Science, Columbia University, New York."},{"key":"10.1016\/S0065-2458(08)60462-3_bib16","series-title":"On the Cost of Computing Roots of Polynomials","author":"Kuhn","year":"1983"},{"key":"10.1016\/S0065-2458(08)60462-3_bib17","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1090\/S0025-5718-1970-0285086-9","article-title":"Optimal approximation in Hilbert spaces with reproducing kernel functions","volume":"24","author":"Larkin","year":"1970","journal-title":"Math. Comput."},{"key":"10.1016\/S0065-2458(08)60462-3_bib18","series-title":"Machines Who Think","author":"McCorduck","year":"1979"},{"key":"10.1016\/S0065-2458(08)60462-3_bib19","series-title":"Optimal Estimation in Approximation Theory","first-page":"1","article-title":"A survey of optimal recovery","author":"Micchelli","year":"1977"},{"key":"10.1016\/S0065-2458(08)60462-3_bib20","first-page":"583","article-title":"On the best quadrature formulae of the form \u03a3k=1npkf(xk) for some classes of periodic differentiable functions","volume":"38","author":"Motornyj","year":"1974","journal-title":"Dokl. Akad. Nauk SSSR, Ser. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib21","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1137\/0719055","article-title":"Global convergence of a modified Newton iteration for algebraic equations","volume":"19","author":"Murota","year":"1982","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/S0065-2458(08)60462-3_bib22","first-page":"165","article-title":"On the problem of approximation estimate by quadrature formulae","volume":"5","author":"Nikolskij","year":"1950","journal-title":"Usp. Mat. Nauk"},{"key":"10.1016\/S0065-2458(08)60462-3_bib23","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01400965","article-title":"Asymptotic minimum norm quadrature formulae","volume":"24","author":"Pinkus","year":"1975","journal-title":"Numer. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib24","series-title":"Algorithms and Complexity: New Directions and Recent Results","first-page":"21","article-title":"Probabilistic algorithms","author":"Rabin","year":"1976"},{"key":"10.1016\/S0065-2458(08)60462-3_bib25","series-title":"A First Course in Numerical Analysis","author":"Ralston","year":"1978"},{"key":"10.1016\/S0065-2458(08)60462-3_bib26","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/0022-0000(80)90014-8","article-title":"Coping with errors in binary search procedures","volume":"20","author":"Rivest","year":"1980","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0065-2458(08)60462-3_bib27","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.2307\/1911438","article-title":"Effective price mechanisms","volume":"46","author":"Saari","year":"1978","journal-title":"Econometrica"},{"key":"10.1016\/S0065-2458(08)60462-3_bib28","doi-asserted-by":"crossref","first-page":"80","DOI":"10.2307\/2372095","article-title":"Best approximate integration formulas; best approximation formulas","volume":"71","author":"Sard","year":"1949","journal-title":"Am. J. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib29","series-title":"The Fundamental Theorem of Algebra in Terms of Computational Complexity","author":"Sch\u00f6nhage","year":"1982"},{"key":"10.1016\/S0065-2458(08)60462-3_bib30","series-title":"Computational Complexity On the Geometry of Polynomials and a Theory of Cost: Part I","author":"Shub","year":"1982"},{"key":"10.1016\/S0065-2458(08)60462-3_bib31","doi-asserted-by":"crossref","unstructured":"Shub, M., and Smale, S. (1982b). On the average cost of solving polynomial equations. Proc. Rio Conf. Dyn. Syst. 1982","DOI":"10.1007\/BFb0061442"},{"key":"10.1016\/S0065-2458(08)60462-3_bib32","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01459080","article-title":"Bisection is optimal","volume":"40","author":"Sikorski","year":"1982","journal-title":"Numer. Math."},{"key":"10.1016\/S0065-2458(08)60462-3_bib33","series-title":"Optimal Solution of Nonlinear Equations Satisfying a Lipschitz Condition","author":"Sikorski","year":"1983"},{"key":"10.1016\/S0065-2458(08)60462-3_bib34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1981-14858-8","article-title":"The fundamental theorem of algebra and complexity theory","volume":"4","author":"Smale","year":"1981","journal-title":"Bull. Am. Math. Soc."},{"key":"10.1016\/S0065-2458(08)60462-3_bib35","unstructured":"Smolyak, S. A. (1965). On optimal restoration of functions and functionals of them. Candidate Dissertation, Moscow State University (in Russian)."},{"key":"10.1016\/S0065-2458(08)60462-3_bib36_1","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast Monte-Carlo test for primality","volume":"6","author":"Solovay","year":"1977","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60462-3_bib36_2","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/0207009","volume":"7","year":"1978","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0065-2458(08)60462-3_bib37_1","first-page":"20","article-title":"Optimal search for a zero of function satisfying Lipschitz's condition","volume":"16","author":"Sukharev","year":"1976","journal-title":"Zh. Vychisl. Mat. Mat. Fiz."},{"key":"10.1016\/S0065-2458(08)60462-3_bib37_2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0041-5553(76)90069-0","article-title":"Optimal search for the roots of a function satisfying a Lipschitz condition","volume":"16","year":"1976","journal-title":"USSR Comput. Math. Math. Phys. (Engl. Transl.)"},{"key":"10.1016\/S0065-2458(08)60462-3_bib38","doi-asserted-by":"crossref","unstructured":"Traub, J. F. (1961). On functional iteration and the calculation of roots. Prepr. Pap., Natl. ACM Conf., 16th, 1961, Sess. 5A-1, pp. 1\u20134.","DOI":"10.1145\/800029.808506"},{"key":"10.1016\/S0065-2458(08)60462-3_bib39","series-title":"Iterative Methods for the Solution of Equations","author":"Traub","year":"1964"},{"key":"10.1016\/S0065-2458(08)60462-3_bib40","first-page":"685","article-title":"Parallel algorithms and parallel computational complexity","volume":"74","author":"Traub","year":"1974","journal-title":"Inf. Process."},{"key":"10.1016\/S0065-2458(08)60462-3_bib41","unstructured":"Traub, J. F. (1978). The influence of algorithms and heuristics on mathematics, science, and education. Proc. Anniv. Symp., I. R. I. A., 10th 1978"},{"key":"10.1016\/S0065-2458(08)60462-3_bib42","series-title":"Algorithms and Complexity: New Directions and Recent Results","first-page":"103","article-title":"Optimal linear information for the solution of nonlinear equations","author":"Traub","year":"1976"},{"key":"10.1016\/S0065-2458(08)60462-3_bib43","series-title":"A General Theory of Optimal Algorithms","author":"Traub","year":"1980"},{"key":"10.1016\/S0065-2458(08)60462-3_bib44","series-title":"On the Optimal Solution of Large Linear Systems","author":"Traub","year":"1980"},{"key":"10.1016\/S0065-2458(08)60462-3_bib45","unstructured":"Traub, J. F., Wasilkowski, G. W., and Wo\u017aniakowski, H. (1981). Average case optimality for linear problems. Theor. Comput. Sci. (to be published)."},{"key":"10.1016\/S0065-2458(08)60462-3_bib46","series-title":"Information, Uncertainty, Complexity","author":"Traub","year":"1983"},{"key":"10.1016\/S0065-2458(08)60462-3_bib47","series-title":"Introduction to the Mathematics of Inversion in Remote Sensing and Indirect Measurements","author":"Twomey","year":"1977"},{"key":"10.1016\/S0065-2458(08)60462-3_bib48","unstructured":"Wasilkowski, G. W. (1982). Inverse function problem. Rep. Dept. of Computer Science, Columbia University, New York. (To be published in J. Inf. Process. Cybernetics\u2013EIK.)"},{"key":"10.1016\/S0065-2458(08)60462-3_bib49","series-title":"Average Case Optimal Algorithms in Hilbert Spaces","author":"Wasilkowski","year":"1982"},{"key":"10.1016\/S0065-2458(08)60462-3_bib50","unstructured":"Werschulz, A. G. (1982a). Does increased regularity lower complexity. Rep. Division of Science and Mathematics, Fordham University and Dept. of Computer Science, Columbia University. (To be published in Math. Comput.)"},{"key":"10.1016\/S0065-2458(08)60462-3_bib51","unstructured":"Werschulz, A. G. (1982b). Measuring uncertainty without a norm. Rep. Division of Science and Mathematics, Fordham University and Dept. of Computer Science, Columbia University. (To be published in Aequationes Math.)"},{"key":"10.1016\/S0065-2458(08)60462-3_bib52","series-title":"Counterexamples in Optimal Quadrature","author":"Werschulz","year":"1983"},{"key":"10.1016\/S0065-2458(08)60462-3_bib53","series-title":"Can Adaption Help On the Average?","author":"Wo\u017aniakowski","year":"1982"}],"container-title":["Advances in Computers","Advances in Computers Volume 23"],"original-title":[],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T23:45:08Z","timestamp":1559951108000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0065245808604623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1984]]},"references-count":56,"URL":"https:\/\/doi.org\/10.1016\/s0065-2458(08)60462-3","relation":{},"ISSN":["0065-2458"],"issn-type":[{"value":"0065-2458","type":"print"}],"subject":[],"published":{"date-parts":[[1984]]}}}