{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:43:23Z","timestamp":1776797003234,"version":"3.51.2"},"reference-count":35,"publisher":"American Mathematical Society (AMS)","issue":"287","license":[{"start":{"date-parts":[[2014,8,1]],"date-time":"2014-08-01T00:00:00Z","timestamp":1406851200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    We study function approximation in the average case setting for spaces of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"normal infinity\">\n                        <mml:semantics>\n                          <mml:mi mathvariant=\"normal\">\n                            \u221e\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\infty<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -variate functions that have a weighted tensor product form and are endowed with a Gaussian measure that also has a weighted tensor product form. Moreover, we assume that the cost of function evaluation depends on the number of active variables and we allow it to be from linear to exponential. We provide a necessary and sufficient condition for the problem to be polynomially tractable and derive the exact value of the tractability exponent. In particular, the approximation problem is polynomially tractable under modest conditions on weights even if the function evaluation cost is exponential in the number of active variables. The problem is weakly tractable even if this cost is doubly exponential. These results hold for algorithms that can use unrestricted linear information. Similar results hold for weighted\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper L 2\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mi>L<\/mml:mi>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">L_2<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    approximation, a special case of function approximation problems considered in this paper, and algorithms restricted to those that use only function samplings.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2013-02759-7","type":"journal-article","created":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T13:06:17Z","timestamp":1375362377000},"page":"1319-1336","source":"Crossref","is-referenced-by-count":7,"title":["Average case tractability of approximating \u221e-variate functions"],"prefix":"10.1090","volume":"83","author":[{"given":"G.","family":"Wasilkowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2013,8,1]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1137\/050645142","article-title":"A stochastic collocation method for elliptic partial differential equations with random input data","volume":"45","author":"Babu\u0161ka, Ivo","year":"2007","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"4","key":"2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10208-008-9029-x","article-title":"Infinite-dimensional quadrature and approximation of distributions","volume":"9","author":"Creutzig, Jakob","year":"2009","journal-title":"Found. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1615-3375","issn-type":"print"},{"key":"3","doi-asserted-by":"crossref","unstructured":"A. Das, Field Theory: A Path Integral Approach, Lecture Notes in Physics, Vol.52, World Scientific, Singapore, 1993.","DOI":"10.1142\/2025"},{"key":"4","doi-asserted-by":"crossref","unstructured":"C. DeWitt-Morette (editor), Special Issue on Functional Integration, J.Mathematical Physics 36 (1995).","DOI":"10.1063\/1.531039"},{"key":"5","unstructured":"D. Duffie, Dynamic Asset Pricing Theory, Princeton University, Princeton, NJ, 1996."},{"key":"6","doi-asserted-by":"crossref","unstructured":"R. P. Egorov, P. I. Sobolevsky, and L. A. Yanovich, Functional Integrals: Approximate Evaluation and Applications, Kluver Academic, Dordrecht, 1993.","DOI":"10.1007\/978-94-011-1761-6"},{"key":"7","isbn-type":"print","volume-title":"Quantum mechanics and path integrals","author":"Feynman, Richard P.","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9780486477220"},{"key":"8","unstructured":"M. Gnewuch, Infinite-dimensional integration on weighted Hilbert spaces, submitted."},{"issue":"3","key":"9","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/j.jco.2010.02.002","article-title":"Multi-level Monte Carlo algorithms for infinite-dimensional integration on \u211d^{\u2115}","volume":"26","author":"Hickernell, Fred J.","year":"2010","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-540-74496-2_27","article-title":"Tractability of linear multivariate problems in the average case setting","author":"Hickernell, Fred","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540744955"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1023\/A:1018948631251","article-title":"Integration and approximation in arbitrary dimensions","volume":"12","author":"Hickernell, F. J.","year":"2000","journal-title":"Adv. Comput. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/1019-7168","issn-type":"print"},{"key":"12","unstructured":"J. C. Hull, Option, Futures, and Other Derivatives, 5th ed., Upper Saddle River, New Jersey, 2002."},{"key":"13","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1142\/1332","volume-title":"Path-integral methods and their applications","author":"Khandekar, D. C.","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/9810205635"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1142\/1081","volume-title":"Path integrals in quantum mechanics, statistics, and polymer physics","author":"Kleinert, Hagen","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/9810201966"},{"issue":"6","key":"15","doi-asserted-by":"publisher","first-page":"3351","DOI":"10.1137\/110845537","article-title":"Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients","volume":"50","author":"Kuo, Frances Y.","year":"2012","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"issue":"5","key":"16","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/j.jco.2009.12.003","article-title":"Liberating the dimension","volume":"26","author":"Kuo, Frances Y.","year":"2010","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"270","key":"17","doi-asserted-by":"publisher","first-page":"953","DOI":"10.1090\/S0025-5718-09-02319-9","article-title":"On decompositions of multivariate functions","volume":"79","author":"Kuo, F. Y.","year":"2010","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","unstructured":"R. Merton, Continuous\u2013Time Finance, Basil Blackwell, Oxford, 1990."},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/978-3-642-04107-5_35","article-title":"Monte Carlo simulation of stochastic integrals when the cost of function evaluation is dimension dependent","author":"Niu, Ben","year":"2009","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642041068"},{"issue":"3-4","key":"20","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.jco.2010.08.001","article-title":"Deterministic multi-level algorithms for infinite-dimensional integration on \u211d^{\u2115}","volume":"27","author":"Niu, Ben","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"5","key":"21","doi-asserted-by":"publisher","first-page":"2309","DOI":"10.1137\/060663660","article-title":"A sparse grid stochastic collocation method for partial differential equations with random input data","volume":"46","author":"Nobile, F.","year":"2008","journal-title":"SIAM J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0036-1429","issn-type":"print"},{"key":"22","series-title":"EMS Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4171\/026","volume-title":"Tractability of multivariate problems. Vol. 1: Linear information","volume":"6","author":"Novak, Erich","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190265"},{"key":"23","series-title":"EMS Tracts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.4171\/084","volume-title":"Tractability of multivariate problems. Volume II: Standard information for functionals","volume":"12","author":"Novak, Erich","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783037190845"},{"issue":"1","key":"24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0885-064X(90)90009-3","article-title":"On the average complexity of multivariate problems","volume":"6","author":"Papageorgiou, A.","year":"1990","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"6","key":"25","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1016\/j.jco.2011.01.006","article-title":"Tractability of infinite-dimensional integration in the worst case and randomized settings","volume":"27","author":"Plaskota, L.","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"2","key":"26","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jcph.2000.6599","article-title":"A new algorithm and worst case complexity for Feynman-Kac path integration","volume":"164","author":"Plaskota, Leszek","year":"2000","journal-title":"J. Comput. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9991","issn-type":"print"},{"key":"27","series-title":"Computer Science and Scientific Computing","isbn-type":"print","volume-title":"Information-based complexity","author":"Traub, J. F.","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0126975450"},{"issue":"4","key":"28","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1216\/RMJ-1986-16-4-727","article-title":"Optimal algorithms for linear problems with Gaussian measures","volume":"16","author":"Wasilkowski, G. W.","year":"1986","journal-title":"Rocky Mountain J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0035-7596","issn-type":"print"},{"issue":"3","key":"29","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1016\/0885-064X(86)90002-6","article-title":"Information of varying cardinality","volume":"2","author":"Wasilkowski, G. W.","year":"1986","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"3","key":"30","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.jco.2011.12.002","article-title":"Liberating the dimension for \ud835\udc3f\u2082-approximation","volume":"28","author":"Wasilkowski, G. W.","year":"2012","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"1","key":"31","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0021-9045(86)90043-2","article-title":"Average case optimal algorithms in Hilbert spaces","volume":"47","author":"Wasilkowski, G. W.","year":"1986","journal-title":"J. Approx. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0021-9045","issn-type":"print"},{"issue":"4","key":"32","doi-asserted-by":"publisher","first-page":"2071","DOI":"10.1063\/1.531493","article-title":"On tractability of path integration","volume":"37","author":"Wasilkowski, Grzegorz W.","year":"1996","journal-title":"J. Math. Phys.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-2488","issn-type":"print"},{"issue":"1","key":"33","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.jco.2010.08.004","article-title":"Liberating the dimension for function approximation","volume":"27","author":"Wasilkowski, G. W.","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"issue":"5","key":"34","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jco.2011.02.002","article-title":"Liberating the dimension for function approximation: standard information","volume":"27","author":"Wasilkowski, G. W.","year":"2011","journal-title":"J. Complexity","ISSN":"https:\/\/id.crossref.org\/issn\/0885-064X","issn-type":"print"},{"key":"35","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1142\/0178","volume-title":"Introduction to path-integral methods in physics and polymer science","author":"Wiegel, F. W.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/9971978709"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02759-7\/S0025-5718-2013-02759-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02759-7\/S0025-5718-2013-02759-7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:53:46Z","timestamp":1776794026000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-287\/S0025-5718-2013-02759-7\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,1]]},"references-count":35,"journal-issue":{"issue":"287","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["S0025-5718-2013-02759-7"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2013-02759-7","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8,1]]}}}