Funding: FWF
Funding period: Sep 2021 - Aug 2025
Project number: P34808


  • Peter Kritzer (PI, project leader, RICAM, since Sep 2021)
  • Aicke Hinrichs (PI, national research partner, JKU, since Sep 2021)
  • Mathias Sonnleitner (PhD student, JKU, Sep 2021)
  • Vishnupriya Anupindi (PostDoc, RICAM, since Aug 2022)
  • Florian Aichinger (PhD student, RICAM, since Feb 2023)


The topic of the project is in the field of Information-Based Complexity (IBC), which is a sub-field of mathematics concerned with the following questions: if a mathematical problem depends on a large number of variables, how much information about the problem is required to solve it approximately, but not exceeding a certain error threshold? How does the amount of required information change if the number of variables and/or the error threshold change?

To quantify the dependence of a problem on the number of variables and the error threshold, this can be done by using a concept called tractability, and studying the tractability of various computational problems is among the core questions of IBC. Various notions of tractability, quantifying the dependence on the number of variables and the threshold, exist in the literature.

This project is devoted to the study of IBC, and, in particular tractability, in frameworks that have so far not been studied extensively. Doing so, we hope to push the boundaries of the research field further, and to make make the theory more useful for applications. To give an example, we plan to consider problems where we allow the number of variables to be unbounded, which is an additional challenge in comparison to the standard settings. This and all other problems that shall be dealt with in the course of the project are motivated by recent publications of experts in the field of IBC.



  • A. Ebert, P. Kritzer, F. Pillichshammer. Tractability of approximation in the weighted Korobov spaces in the worst-case setting. In: Z. Botev et. al (eds.). Advances in Modeling and Simulation, 131-150, Springer, Cham, 2022.
  • M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter. Countable tensor products of Hermite spaces and spaces of Gaussian kernels. J. Complexity 71, 101654, 2022.
  • A. Hinrichs, J. Prochno, M. Sonnleitner. Random sections of $\ell_p$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators. Submitted, 2021.
  • D. Krieg, M. Sonnleitner. Function recovery on manifolds using scattered data. Submitted, 2022.
  • P. Kritzer. A note on the CBC-DBD construction of lattice rules with general positive weights. J. Complexity 78, 101721, 2023.
  • P. Kritzer, O. Osisiogu. On a reduced digit-by-digit component-by-component construction of lattice point sets. Submitted, 2022.


  • F. Aichinger. Modeling large spot price deviations in electricity markets. German Probability and Statistics Days 2023 (GPSD). Mar. 8, 2023. Essen, Germany.
  • P. Kritzer. Fast computation of matrix-vector products using reduced lattice points. 9th Workshop on High-Dimensional Integration (HDA 2023). Feb. 20, 2023. Canberra, Australia.
  • P. Kritzer. The fast reduced QMC matrix-vector multiplication. Workshop on Approximation and Geometry. Oct. 13, 2022. Bedlewo, Poland.
  • P. Kritzer. Various search algorithms for good lattice rules. SIAM Conference on Uncertainty Quantification. Apr. 13, 2022. Atlanta (virtually), USA.
  • P. Kritzer. Digit-by-digit constructions of good lattice rules. ESI-Workshop on Adaptivity, High-Dimensionality, and Randomness. Apr. 8, 2022. Vienna, Austria.
  • M. Sonnleitner. Random sections of p-ellipsoids and optimal recovery. Austrian Stochastics Days. Sep. 10, 2021. Leoben, Austria.