Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An intractability result for multiple integration

Authors: I. H. Sloan and H. Woźniakowski
Journal: Math. Comp. 66 (1997), 1119-1124
MSC (1991): Primary 41A55, 65D30
MathSciNet review: 1401946
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that the problem of multiple integration in the Korobov class $E_{\alpha ,d}$ is intractable since the number of function evaluations required to achieve a worst case error less than $1$ is exponential in the dimension.

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

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 41A55, 65D30

Retrieve articles in all journals with MSC (1991): 41A55, 65D30

Additional Information

I. H. Sloan
Affiliation: School of Mathematics, University of New South Wales, Sydney 2052, Australia

H. Woźniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warsaw, Poland

Keywords: Multiple integration, intractability, lattice rules
Received by editor(s): December 21, 1995
Received by editor(s) in revised form: May 3, 1996
Additional Notes: The first author was partially supported by the Australian Research Council.
The second author was partially supported by the National Science Foundation and the Air Force Office of Scientific Research.
Article copyright: © Copyright 1997 American Mathematical Society