Numerical Algorithms Group Prof. Dr. Stefan Heinrich
Publications
Randomized Complexity of Mean Computation and the Adaption Problem
   [preprint]
see also http://arxiv.org/abs/2401.14100
Randomized Complexity of Parametric Integration and the Role of Adaption II. Sobolev Spaces
J. Complexity 82 (2024), 101823.    [preprint]
see also http://arxiv.org/abs/2306.13499
Randomized Complexity of Vector-Valued Approximation
to appear in: A. Hinrichs, P. Kritzer, F. Pillichshammer (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2022, Springer-Verlag.    [preprint]
see also http://arxiv.org/abs/2306.13697
Randomized Complexity of Parametric Integration and the Role of Adaption I. Finite Dimensional Case
J. Complexity 82 (2024), 101821.    [preprint]
see also http://arxiv.org/abs/2306.13471
Lower bounds for the number of random bits in Monte Carlo algorithms
In: Keller, A. (ed) Monte Carlo and Quasi-Monte Carlo Methods. MCQMC 2020. Springer Proceedings in Mathematics & Statistics, vol 387, pp.131-147, Springer, 2022.    [preprint]
see also http://arxiv.org/abs/2012.12774
On the power of restricted Monte Carlo algorithms
2018 MATRIX Annals, Springer, 2020, pp. 45--59.    [preprint]
Complexity of stochastic integration in Sobolev classes
J. Math. Anal. Appl. 476 (2019), 177-195    [preprint]
On the complexity of computing the Lq norm
J. Complexity 49 (2018), 1-26   [preprint]
Lower complexity bounds for parametric stochastic Itô integration
Monte Carlo and quasi-Monte Carlo methods, MCQMC 2016. Proceedings of the 12th international conference on `Monte Carlo and quasi-Monte Carlo methods in scientific computing', Stanford, CA, August 14-19, 2016 ( A. B. Owen, P. W. Glynn, eds.), Springer Proceedings in Mathematics & Statistics 241, pp. 295-312, Berlin 2018    [preprint]
On the complexity of parametric ODEs and related problems
Contemporary Computational Mathematics - A Celebration of the 80th Birthday of Ian Sloan (J. Dick, F. Y. Kuo, H. Wozniakowski, Eds.), pp. 567-595, Springer, Berlin, 2018    [preprint]
Complexity of Banach space valued and parametric stochastic Itô integration
         with Th. Daun
J. Complexity 40 (2017), 100-122    [preprint]
Complexity of parametric initial value problems for systems of ODEs
         with Th. Daun
Mathematics and Computers in Simulation 135, 72-85 (May 2017), doi:10.1016/j.matcom.2015.04.008    [preprint]
Complexity of parametric integration in various smoothness classes
         with Th. Daun
J. Complexity 30, No. 6, 750-766 (2014).    [preprint]
Complexity of parametric initial value problems in Banach spaces
         with Th. Daun
J. Complexity 30, No. 4, 392-429 (2014).    [preprint]
On the randomized complexity of Banach space valued integration
         with A. Hinrichs
Studia Math. 223, 205-215 (2014).    [preprint]
Complexity of initial value problems in Banach spaces
J. Math. Phys. Anal. Geom. 9, 73-101 (2013).    [preprint]
Complexity of Banach space valued and parametric integration
         with Th. Daun
Monte Carlo and Quasi-Monte Carlo Methods 2012 (J. Dick, F. Y. Kuo, G. W. Peters, I. H. Sloan, eds.), Springer Proceedings in Mathematics and Statistics 65, pp. 297-316, Berlin, 2013.    [preprint]
Stochastic approximation of functions and applications
L. Plaskota, H. Wozniakowski (ed.), Monte Carlo and Quasi-Monte Carlo Methods 2010, Selected papers based on the presentations at the 9th international conference on Monte Carlo and quasi Monte Carlo methods in scientific computing, Warsaw, Poland, August 15--20, 2010, Springer Proceedings in Mathematics & Statistics 23, pp. 95-131, Berlin, 2012 .    [preprint]
Ultrastability of n-th minimal errors
J. Complexity 28, No. 4, 440-458 (2012) .    [preprint]
The randomized complexity of indefinite integration
         with B. Milla
J. Complexity 27, No. 3-4, 352-382 (2011) .    [preprint]
Randomized approximation of Sobolev embeddings. III.
J. Complexity 25, No. 5, 473-507 (2009).    [preprint]
Randomized approximation of Sobolev embeddings. II.
J. Complexity 25, No. 5, 455-472 (2009).    [preprint]
The randomized complexity of initial value problems
with B. Milla
Journal of Complexity 24, No. 2, 77-88 (2008)   [preprint]
Randomized approximation of Sobolev embeddings
Keller, Alexander (ed.) et al., Monte Carlo and quasi-Monte Carlo methods 2006. Selected papers based on the presentations at the 7th international conference `Monte Carlo and quasi-Monte Carlo methods in scientific computing', Ulm, Germany, August 14--18, 2006. Berlin: Springer. 445-459 (2008)  [preprint]
Quantum lower bounds by entropy numbers
J. Complexity 23, No. 4-6, 793-801 (2007) Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0611294
Numerical analysis on a quantum computer
Lirkov, Ivan (ed.) et al., Large-scale scientific computing. 5th international conference, LSSC 2005, Sozopol, Bulgaria, June 6--10, 2005. Revised papers. Berlin: Springer. Lecture Notes in Computer Science 3743, 28-39 (2006)  [preprint]
The quantum query complexity of elliptic PDE
J. Complexity 22, No. 5, 691-725 (2006)   Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0512241
The randomized information complexity of elliptic PDE
J. Complexity 22, No. 2, 220--249 (2006)  [preprint]
Monte Carlo Approximation of weakly singular integral operators
J. Complexity 22, No. 2, 192--219 (2006)   [preprint]
Quantum  Complexity of Numerical Problems
Cucker, Felipe (ed.) et al., Foundations of computational mathematics: Minneapolis 2002 (FoCM 2002). Selected papers based on the plenary talks presented at FoCM 2002, Minneapolis, MN, USA, August 5--14, 2002. Cambridge: Cambridge University Press. London Mathematical Society Lecture Note Series 312, 76-95 (2004)   [preprint]
On the Power of Quantum Algorithms for Vector Valued Mean Computation
Paper submitted to: Monte Carlo Methods and Applications. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0403109
Quantum Approximation I. Embeddings of Finite Dimensional L_p Spaces
Journal of Complexity 20 (2004), 5-26. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0305030
Quantum Approximation II. Sobolev Embeddings
Journal of Complexity 20 (2004) 27-45. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0305031
Quantum Boolean Summation with Repetitions in the  Worst-Average Setting 
with M. Kwas and H. Wozniakowski
In: Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, Ed.), pp. 243-258, Springer-Verlag, 2004. 
[ps]  [pdf] 
How Many Random Bits Do We Need for Monte Carlo Integration?
with E. Novak and H. Pfeiffer
In: Monte Carlo and Quasi-Monte Carlo Methods 2002 (H. Niederreiter, Ed.), pp. 27-49, Springer-Verlag, 2004. 
[ps]  [pdf] 
Quantum Integration in Sobolev Classes
Journal of Complexity 19 (2003), 19-42. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0112153
From Monte Carlo to Quantum Computation
Proceedings of the 3rd IMACS Seminar on Monte Carlo Methods MCM2001, Salzburg, Special Issue of Mathematics and Computers in Simulation (Guest Eds.: K. Entacher, W. Ch. Schmid, A. Uhl) 62 (2003), 219--230.
 [ps]  [pdf] 
On a Problem in Quantum Summation
with E. Novak
Journal of Complexity 19 (2003), 1-18. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0109038
Optimal Quadrature for Haar Wavelet Spaces
with F. J. Hickernell and R.-X. Yue
Math. Comput. 73 No. 245 (2004), 259-277.
 [ps]  [pdf] 
Quantum Summation with an Application to Integration
Journal of Complexity 18 (2002), 1-50. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0105116
Optimal Summation and Integration by Deterministic, Randomized, and Quantum Algorithms
with E. Novak
 in:  K.-T. Fang, F. J. Hickernell, H. Niederreiter (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2000, Springer-Verlag, Berlin, 2002, pp. 50--62. Abstract and paper avaibable at http://arXiv.org/abs/quant-ph/0105114
Multilevel Monte Carlo methods
Margenov, S. (ed.) et al., Large-scale scientific computing. 3rd international conference,
LSSC 2001, Sozopol, Bulgaria, June 6-10, 2001. Revised papers. Berlin: Springer.
Lect. Notes Comput. Sci. 2179, 58-67 (2001)  [preprint]
The inverse of the star-discrepancy depends linearly on the dimension
with E. Novak, G. W. Wasilkowski, H. Wozniakowski
Acta Arithmetica XCVI.3 (2001), 279-302  [preprint]
The multilevel method of dependent tests
Advances in Stochastic Simulation Methods (N. Balakrishnan,V.B. Melas, S. Ermakov, editors), pp. 47-62. Birkhäuser, Boston, Basel, Berlin, 2000. [preprint]
Variance reduction by means of deterministic computation: Collision estimate 
J. Statist. Planning and Inference 85 (2000), 159-169  [preprint]
Monte Carlo complexity of parametric integration 
with E. Sindambiwe
J. Complexity 15 (1999), 317-341 [preprint]
Wavelet Monte Carlo methods for the global solution of integral equations 
Proceedings of the Third International Conference on Monte Carlo and Quasi-Monte Carlo Methods, Claremont 1998 (H. Niederreiter and J. Spanier, editors), pp. 227 - 237, Springer 1999  [preprint]
Monte Carlo complexity of global solution of integral equations 
J. Complexity 14, No.2, 151-175 (1998). [preprint]
A multilevel version of the method of dependent tests 
Proceedings of the 3rd St. Petersburg Workshop on Simulation, S. M. Ermakov, Y. N. Kashtanov and V. B. Melas, editors, pp. 31 - 35, St. Petersburg University Press, 1998
Computing discrepancies related to spaces of smooth periodic functions 
with K. Frank
Niederreiter, Harald (ed.) et al., Monte Carlo and quasi-Monte Carlo methods 1996. Proceedings of a conference at the University of Salzburg, Austria, July 9-12, 1996. Berlin: Springer. Lect. Notes Stat., Springer-Verlag. 127, 238-250 (1997).
Using the Galerkin method for variance reduction 
in: "Mathematical methods in stochastic simulation and experimental design", Proceedings of the Second St. Petersburg Workshop on Simulation, Publishing House of Saint Petersburg University, 1996, pp. 56 - 59
Computing discrepancies of Smolyak quadrature rules 
with K. Frank
J. Complexity 12, No.4, 287-314 (1996).
Information complexity of multivariate Fredholm integral equations in Sobolev classes 
with K. Frank and S. Pereverzev
J. Complexity 12, No.1, 17-34 (1996).
Complexity theory of Monte Carlo algorithms 
Renegar, James (ed.) et al., The mathematics of numerical analysis. 1995 AMS-SIAM summer seminar in applied mathematics, July 17 - August 11, 1995, Park City, UT, USA. Providence, RI: American Mathematical Society. Lect. Appl. Math. 32, 405-419 (1996).
Efficient algorithms for computing the $L_2$-discrepancy 
Math. Comput. 65, No.216, 1621-1633 (1996).
Variance reduction for Monte Carlo methods by means of deterministic numerical computation. 
Monte Carlo Methods Appl. 1, No.4, 251-277 (1995).
Complexity of local solution of integral equations 
with K. Frank
Schock, Eberhard (ed.), Beiträge zur Angewandten Analysis und Informatik. Helmut Brakhage zu Ehren. Aachen: Shaker Verlag. Berichte aus der Mathematik. 55-68 (1994).
The Monte Carlo complexity of Fredholm integral equations 
with P. Mathé
Math. Comput. 60, No.201, 257-278 (1993).
Random approximation in numerical analysis 
Bierstedt, Klaus D. (ed.) et al., Functional analysis. Proceedings of the Essen Conference, held in Essen, Germany, November 24 - 30, 1991. New York, NY: Dekker. Lect. Notes Pure Appl. Math. 150, 123-171 (1993).
Complexity of integral equations and relations to $s$-numbers 
J. Complexity 9, No.1, 141-153 (1993).
Lower bounds for the complexity of Monte Carlo function approximation 
J. Complexity 8, No.3, 277-300 (1992).
Efficiency of Monte Carlo algorithms in numerical analysis 
Budach, Lothar (ed.), Fundamentals of computation theory. 8th international conference, FCT '91, Gosen, Germany, September 9-13, 1991. Proceedings. Berlin etc.: Springer-Verlag. Lect. Notes Comput. Sci. 529, 33-44 (1991).
Parallel information-based complexity 
with J.-D. Kern
J. Complexity 7, No.4, 339-370 (1991).
Corrections to "Probabilistic analysis of numerical methods for integral equations" 
J. Integral Equations Appl. 3, No.3, 469-472 (1991).
Probabilistic analysis of numerical methods for integral equations 
J. Integral Equations Appl. 3, No.2, 289-319 (1991).
Probabilistic complexity analysis for linear problems in bounded domains 
J. Complexity 6, No.3, 231-255 (1990).
Invertibility of random Fredholm operators
Stochastic Anal. Appl. 8, No.1, 1-59 (1990).
On the relation between linear n-widths and approximation numbers
J. Approximation Theory 58, No.3, 315-333 (1989).
s-numbers of integral operators with Hölder continuous kernels over metric compacta
with B. Carl and T. Kühn
J. Funct. Anal. 81, No.1, 54-73 (1988).
A note on elementary equivalence of C(K) spaces
with C. Henson and L. Moore jun.
J. Symb. Logic 52, 368-373 (1987).
Banach space model theory. II: Isomorphic equivalence
with C. Henson
Math. Nachr. 125, 301-317 (1986).
The uniform classification of boundedly compact locally convex spaces
Czech. Math. J. 36(111), 68-71 (1986).
Elementary equivalence of $C_\sigma(K)$ spaces for totally disconnected, compact Hausdorff K
with C. Henson and L. Moore jun.
J. Symb. Logic 51, 135-146 (1986).
On the optimal error of degenerate kernel methods
J. Integral Equations 9, No.3, 251-266 (1985).
Ultrapowers of locally convex spaces and applications II
Math. Nachr. 121, 211-229 (1985).
Embedding maps between Hölder spaces over metric compacta and eigenvalues of integral operators
with T. Kühn
Indagationes Math. 47, 47-62 (1985).
On the asymptotic behaviour of Hilbert numbers
with R. Linde
Math. Nachr. 119, 117-120 (1984).
Ultrapowers of locally convex spaces and applications I 
Math. Nachr. 118, 285-315 (1984). 
A problem in discretization theory related to the approximation property of Banach spaces 
Math. Nachr. 111, 147-152 (1983).
Elementary equivalence of $L_1$-preduals 
with C.W. Henson and L.C.jun. Moore
Banach space theory and its applications, Proc. 1st Romanian-GDR Semin., Bucharest 1981, Lect. Notes Math. 991, 79-90 (1983).
Some open problems in the nonlinear classification of Banach spaces 
with P. Mankiewicz
Banach space theory and its applications, Proc. 1st Romanian-GDR Semin., Bucharest 1981, Lect. Notes Math. 991, 91-95 (1983).
The isomorphic problem of envelopes 
Stud. Math. 73, 41-49 (1982).
Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces 
with P. Mankiewicz
Stud. Math. 73, 225-251 (1982).
Order bounded operators and tensor products of Banach lattices 
with N.J. Nielsen and G.H. Olsen
Math. Scand. 49, 99-127 (1981).
Ultraproducts of $L_1$-predual spaces 
Fundam. Math. 113, 221-234 (1981).
Finite representability and super-ideals of operators 
Diss. Math. 172, 37 P. (1980).
Closed operator ideals and interpolation 
J. Funct. Anal. 35, 397-411 (1980).
Ultraproducts in Banach space theory 
J. Reine Angew. Math. 313, 72-104 (1980).
A characterization of $(\infty,p,q)$-integral operators 
with A. Pietsch
Math. Nachr. 89, 197-202 (1979).
Finite representability of operators 
Operator algebras, ideals, and their applications in theoretical physics, Proc. int. Conf. Leipzig 1977, 33-39 (1978).
Some properties of operator spaces 
Serdica 3, 168-175 (1977).
Weak sequential completeness of Banach operator ideals 
Sib. Math. J. 17, 857-862 (1977).
Linear-topological properties of operator spaces 
Gen. Topol. Relat. mod. Anal. Algebra, Proc. 4th Prague Topol. Symp. 1976, Part B, 156-158 (1977).
Strongly exposed and conical points in the projective tensor product (Russian) 
Teor. Funkts., Funkts. Anal. Prilozh. 22, 146-154 (1975).
Approximation properties in tensor products 
Math. Notes 17, 269-272 (1975). translation from Mat. Zametki 17, 459-466 (1975).
The differentiability of the norm in spaces of operators
Funct. Anal. Appl. 9, 360-362 (1975); translation from Funkts. Anal. Prilozh. 9, No.4, 93-94 (1974).
The reflexivity of the Banach space L(E,F) 
Funct. Anal. Appl. 8, 186-187 (1974); translation from Funkts. Anal. Prilozh. 8, No.2, 97-98 (1974).