Project

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

Team

  • Peter Kritzer (PI, project leader, RICAM, since Sep 2021)
  • Aicke Hinrichs (PI, national research partner, JKU, Sep 2021 - Dec 2022)
  • Mathias Sonnleitner (PhD student, JKU, Sep 2021)
  • Florian Aichinger (PhD student, RICAM, Feb 2023 - Jul 2024)
  • Vishnupriya Anupindi (PostDoc, RICAM, Aug 2022 - May 2025)
  • Zexin Pan (PostDoc, RICAM, Oct 2024 - Sep 2025)
  • Nicolas Nagel (PostDoc, RICAM, since Mar 2026)

Abstract

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.

 

Publications

  • M. Haase, N. Nagel. Precise asymptotics and exact formulas for tensor product energies of Fibonacci lattices. Submitted, 2026. https://arxiv.org/abs/2605.20895
  • M. Gnewuch, P. Kritzer, K. Ritter. Embeddings of reproducing kernel Hilbert spaces with general weights. Submitted, 2026. https://arxiv.org/abs/2604.27160 
  • Z. Pan, M. Cai, J. Dick, T. Goda, P. Kritzer. Worst-case $L_p$ -approximation of periodic functions using median lattice algorithms. Submitted, 2026. https://arxiv.org/abs/2603.05271
  • Z. Pan, T. Goda, P. Kritzer. Universal $L_2$-approximation using median lattice algorithms. Submitted, 2025. https://arxiv.org/abs/2509.24582
  • Z. Pan, D. Ouyang, Z. He. Quasi-Monte Carlo integration over $\mathbb{R}^s$  with boundary-damping importance sampling. Submitted, 2025. https://arxiv.org/abs/2509.07509
  • V.N.P. Ho, A.B. Owen, Z. Pan. Quasi-Monte Carlo with one categorical variable. Submitted, 2025. https://arxiv.org/abs/2506.16582
  • Z. Pan. Dimension-independent convergence rates of randomized nets using median-of-means. To appear in: Math. Comp., 2026. https://arxiv.org/abs/2505.13815
  • Z. Pan. Quasi-Monte Carlo confidence intervals using quantiles of randomized nets. To appear in: Ann. Stat., 2026.  https://arxiv.org/abs/2504.19138
  • Z. Pan, P. Kritzer, T. Goda. $L_2$-approximation using median lattice algorithms.To appear in: Constr. Approx., 2026. https://arxiv.org/abs/2501.15331
  • V. Anupindi, P. Kritzer. Reduced digital nets. In: B. Feng, C. Lemieux (eds.). Monte Carlo and Quasi-Monte Carlo Methods 2024, 169-187. Springer, Cham, 2026. https://arxiv.org/abs/2501.13659
  • Z. Pan. Automatic optimal-rate convergence of randomized nets using median-of-means. Math. Comp. 95, 1415-1446, 2026.  https://arxiv.org/abs/2411.01397
  • P.A. Guth, P. Kritzer, K. Kunisch. Quasi-Monte Carlo integration for feedback control under uncertainty. SIAM J. Uncertain. Quantif. 13, 1228-1264, 2025.  https://arxiv.org/abs/2409.15537
  • V. Anupindi, P. Kritzer. Column reduced digital nets. Numer. Alg. 101, 1451-1473, 2026. https://arxiv.org/abs/2406.10850
  • M. Gnewuch, P. Kritzer, A.B. Owen, Z. Pan. Computable error bounds for quasi-Monte Carlo using points with non-negative local discrepancy. Inf. Inference 13, iaae021, 2024. https://arxiv.org/abs/2309.04209
  • C. Laudage, S. Desmettre, F. Aichinger. Pricing of geometric Asian options in the Volterra-Heston model. Rev. Deriv. Res. 28, 5, 2025. https://arxiv.org/abs/2402.15828
  • P. Kritzer. Selected aspects of tractability analysis. J. Complexity 84, 101869, 2024. https://arxiv.org/abs/2402.02396 
  • D. Krieg, P. Kritzer. Homogeneous algorithms and solvable problems on cones. J. Complexity 83, 101840, 2024. https://arxiv.org/abs/2311.15767 
  • J. Dick, A. Ebert, L. Herrmann, P. Kritzer, M. Longo. The fast reduced QMC matrix-vector product. J. Comput. Appl. Math. 440, 115642, 2024. https://arxiv.org/abs/2305.11645
  • O. Emenike, F.J. Hickernell, P. Kritzer. A unified treatment of tractability for approximation problems defined on Hilbert spaces. J. Complexity 84, 101856, 2024. https://arxiv.org/abs/2310.17777
  • C. Laudage, F. Aichinger, S. Desmettre. A comparative study of factor models for different periods of the electricity spot price market. J. Commod Mark. 36, 100435, 2024. https://arxiv.org/abs/2306.07731
  • 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. https://arxiv.org/abs/2201.09940
  • M. Gnewuch, M. Hefter, A. Hinrichs, K. Ritter. Countable tensor products of Hermite spaces and spaces of Gaussian kernels. J. Complexity 71, 101654, 2022. https://arxiv.org/abs/2110.05778
  • A. Hinrichs, J. Prochno, M. Sonnleitner. Random sections of $\ell_p$-ellipsoids, optimal recovery and Gelfand numbers of diagonal operators. J. Approximation Th. 293, 105919, 2023. https://arxiv.org/abs/2109.14504
  • D. Krieg, M. Sonnleitner. Function recovery on manifolds using scattered data. J. Approximation Th. 305, 106098, 2025. https://arxiv.org/abs/2109.04106
  • P. Kritzer. A note on the CBC-DBD construction of lattice rules with general positive weights. J. Complexity 78, 101721, 2023. https://arxiv.org/abs/2208.13610
  • P. Kritzer, O. Osisiogu. On a reduced component-by-component digit-by-digit construction of lattice point sets. Uniform Distribution Theory 18 (1), 97-140, 2023. https://arxiv.org/abs/2211.13237

Talks

  • P. Kritzer. Function space embeddings and problems with infinitely many variables. University of New South Wales, Feb. 11, 2026. Sydney, Australia.
  • P. Kritzer. Function spaces and approximation problems with an unbounded number of variables. University of Passau, Dec. 9, 2025. Passau, Germany.
  • P. Kritzer. Function spaces and approximation problems with infinitely many variables. Research Seminar of the Department of Financial Mathematics of JKU Linz, Dec. 4, 2025. Linz, Austria.
  • P. Kritzer. $L_2$-approximation using median lattice rules. Workshop on Approximation, Geometry, and Probability in High Dimensions. Sep. 22, 2025. Bedlewo, Poland.
  • P. Kritzer. Median lattice rules for function approximation. HDA 2025, Sep. 11, 2025, Bonn, Germany. 
  • Z. Pan. Dimension-independent convergence rates of median randomized nets. HDA 2025, Sep. 10, 2025, Bonn, Germany.
  • Z. Pan. QMC confidence intervals using quantiles of randomized nets. MCM 2025, Jul. 31, 2025, Chicago, USA.
  • P. Kritzer. Median lattice rules for function approximation. MCM 2025, Jul. 29, 2025, Chicago, USA.
  • Z. Pan. L2-approximation using median lattice algorithms. 30th Biennial Numerical Analysis Conference, Jun. 27, 2025, Glasgow, UK.
  • P. Kritzer. Function space embeddings and $L_\infty$-approximation with infinitely many variables. CTAC 2024, Nov. 21, 2024, Melbourne, Australia.
  • V. Anupindi. Pseudorandom sequences: Applications, quality measures and constructions. Oct. 15, 2024, Invited talk, Nagoya University, Japan.
  • V. Anupindi. Properties of pseudorandom numbers from genus 2 curves. Oct. 10, 2024, Invited talk, Kyushu University, Japan.
  • V. Anupindi. On the linear complexity profile of some sequences constructed from curves. Sep. 20, 2024, Invited talk, University of Tokyo, Japan.
  • P. Kritzer. Lattice rules? Lattices rule! Sep. 19, 2024, Invited talk, University of Graz, Austria. 
  • V. Anupindi. Quality parameter for reduced digital nets. JMCQMC 2024, Sep. 17, 2024, Invited talk, University of Tokyo, Japan.
  • P. Kritzer. QMC and nonnegative local discrepancy. MCQMC 2024, Aug. 20, 2024, Waterloo, Canada. 
  • V. Anupindi. Column reduced digital nets. MCQMC 2024, Aug. 19, 2024, Waterloo, Canada (remote).
  • V. Anupindi (Poster presentation). Linear complexity of some sequences from curves of genus 2. Mathematics for post-quantum cryptanalysis (Math PQC). Aug. 8, 2024. Budapest, Hungary.
  • P. Kritzer. QMC and non-negative local discrepancy. Research Seminar of the Department of Financial Mathematics of JKU Linz, Jul. 2, 2024. Linz, Austria.
  • P. Kritzer. Point sets with non-negative local discrepancy and their use in quasi-Monte Carlo rules. Kolloquium des Instituts für Mathematik der Universität Osnabrück, Jun. 19, 2024. Osnabrück, Germany.
  • F. Aichinger. Pricing of geometric Asian options in the Volterra-Heston model. Stochastic Models and Control (SMC) 2024, Feb. 27, 2024. Graz, Austria.
  • P. Kritzer. What lattice rules can do for you. RICAM Colloquium, Jan. 18, 2024. Linz, Austria.
  • V. Anupindi. Reduced digital nets. Linz Algebra Research Day, Dec. 12, 2023. Linz, Austria.
  • P. Kritzer. Quasi-Monte Carlo using points with non-negative local discrepancy. Colloquium on the occasion of Johann Brauchart's 50th Birthday, Oct. 20, 2023. Graz, Austria.
  • P. Kritzer. Tractability analysis (invited overview talk). Dagstuhl Seminar on Algorithms and Complexity for Continuous Problems. Aug. 28, 2023. Dagstuhl, Germany.
  • P. Kritzer. Homogeneous algorithms for linear (?) problems. Foundations of Computational Mathematics. Jun. 20, 2023. Paris, France.
  • V. Anupindi (Poster presentation). Pseudorandom numbers from curves of genus 2. Foundations of Computational Mathematics. Jun. 12-14, 2023. Paris, France.
  • P. Kritzer. Lattice point sets for matrix-matrix products. Workshop on the Occasion of the 20th Anniversary of RICAM. Mar. 28, 2023. Linz, Austria.
  • 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.